题目描述

题目译自 XXXII Olimpiada Informatyczna – I etap Walki robotów

在 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。

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
1 1
2 2

NIE

样例 3

见附加文件下 [wal1ocen.in](file:wal1ocen.in) 和 [wal1ocen.out](file:wal1ocen.out)。

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

样例 4

见附加文件下 [wal2ocen.in](file:wal2ocen.in) 和 [wal2ocen.out](file:wal2ocen.out)。

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

样例 5

见附加文件下 [wal3ocen.in](file:wal3ocen.in) 和 [wal3ocen.out](file:wal3ocen.out)。

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

样例 6

见附加文件下 [wal4ocen.in](file:wal4ocen.in) 和 [wal4ocen.out](file: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](file:wal5ocen.in) 和 [wal5ocen.out](file:wal5ocen.out)。

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

数据范围与提示

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

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