题目背景

原题译自 POI 2024/2025 R1 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}$ 互不相同。即 $s,z$ 都是 $1 \sim n$ 的两个排列。

输出格式

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

4
1 4
2 2
3 3
4 1

TAK

2
1 1
2 2

NIE

见下发 wal1ocen.in

见下发 wal1ocen.out

见下发 wal2ocen.in

见下发 wal2ocen.out

见下发 wal3ocen.in

见下发 wal3ocen.out

见下发 wal4ocen.in

见下发 wal4ocen.out

见下发 wal5ocen.in

见下发 wal5ocen.out

提示

对于样例一，如果在第一场比赛中第一个和第二个机器人对决，第二场比赛中第三个和第四个机器人对决，那么所有机器人都将被淘汰。

对于样例三，该样例满足 $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}<i \leq n$。

对于样例七，该样例满足 $n=5$。

子任务编号	特殊性质	分值
$1$	$n \leq 8$	$10$
$2$	$n \leq 20$
$3$	$n \leq 1000$	$30$
$4$	无特殊性质	$50$