P11385 [POI 2024/2025 R1] Walki robotów

原题译自 [POI 2024/2025 R1 Walki robotów](https://sio2.mimuw.edu.pl/c/oi32-1/p/wal/)。

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

输入的第一行包含一个整数 $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}$ 互不相同。即 $s,z$ 都是 $1 \sim n$ 的两个排列。

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

对于样例一，如果在第一场比赛中第一个和第二个机器人对决，第二场比赛中第三个和第四个机器人对决，那么所有机器人都将被淘汰。 对于样例三，该样例满足 $n=8, s_{i}=i, z_{i}=n-i+1$。 对于样例四，该样例满足 $n=20$，存在一个机器人可以击败所有其他机器人，并且没有机器人可以击败它。 对于样例五，该样例满足 $n=500$，可以将所有机器人配对，使每对机器人互相淘汰。 对于样例六，该样例满足 $n=200000, 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}