题目描述

在 Bajtocji 正在进行一场大型年度机器人锦标赛，其中有 $n$ 个机器人参赛，它们的编号从 $1$ 到 $n$。第 $i$ 个机器人由两个参数描述，$s_i$ 和 $z_i$ ($1 \leq s_i, z_i \leq n$)，分别表示机器人的力量和敏捷度。力量值 $s_i$ 各不相同。敏捷度值 $z_i$ 也各不相同。

锦标赛由一系列单挑比赛组成。在每场比赛中，两个尚未被淘汰的机器人进行对决。在第 $i$ 个机器人对战第 $j$ 个机器人的比赛中，如果 $s_i > s_j$ 或 $z_i > z_j$，那么第 $i$ 个机器人将淘汰第 $j$ 个机器人。相应地，如果 $s_i < s_j$ 或 $z_i < z_j$，那么第 $j$ 个机器人将淘汰第 $i$ 个机器人。请注意，这意味着在同一场比赛中可能会有两个机器人都被淘汰。如果某个机器人没有在比赛中被淘汰，它可以继续参与后续比赛。

锦标赛的直播收视率最高，当最终所有机器人都被淘汰时。你的任务是检查是否可以安排一系列比赛，使得最终所有机器人都被淘汰。

输入格式

输入的第一行包含一个整数 $n$ ($1 \leq n \leq 2 \cdot 10^5$)。接下来的 $n$ 行描述了机器人的信息。第 $i$ 个机器人的描述包含两个整数 $s_i$ 和 $z_i$ ($1 \leq s_i, z_i \leq n$)。保证 $s_1, s_2, \ldots, s_n$ 互不相同。保证 $z_1, z_2, \ldots, z_n$ 互不相同。

输出格式

如果可以安排一系列比赛，使得最终所有机器人都被淘汰，则输出 TAK。否则，输出 NIE。

样例 1

输入

4
1 4
2 2
3 3
4 1

输出

TAK

我们有 $s_1=1, z_1=4, s_2=2, z_2=2, s_3=3, z_3=3, s_4=4, z_4=1$。例如，如果在第一场比赛中第一个和第二个机器人对决，第二场比赛中第三个和第四个机器人对决，那么所有机器人都将被淘汰。

样例 2

输入

2
1 1
2 2

输出

NIE

样例 3

见附加文件下 wal1ocen.in 和 wal1ocen.out。

该样例满足 $n=8$, $s_i=i$ 且 $z_i=n-i+1$ 对每个 $1 \leq i \leq n$。答案是 TAK。

样例 4

见附加文件下 wal2ocen.in 和 wal2ocen.out。

该样例满足 $n=20$，存在一个机器人可以击败所有其他机器人，并且没有机器人可以击败它。答案是 NIE。

样例 5

见附加文件下 wal3ocen.in 和 wal3ocen.out。

该样例满足 $n=500$，可以将所有机器人配对，使每对机器人互相淘汰。答案是 TAK。

样例 6

见附加文件下 wal4ocen.in 和 wal4ocen.out。

该样例满足 $n=2 \cdot 10^5$, $s_i=i$ 且 $z_i=i$ 对 $1 \leq i \leq \frac{n}{2}$，并且 $s_i=i$ 且 $z_i=\frac{3n}{2}-i+1$ 对 $\frac{n}{2} < i \leq n$。答案是 TAK。

样例 7

见附加文件下 wal5ocen.in 和 wal5ocen.out。

该样例满足 $n=5$。答案是 TAK。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
1	$n \leq 8$	10
2	$n \leq 20$
3	$n \leq 1000$	30
4	无附加限制	50