4473: 「POI2014」卡片 Card
内存限制：64 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
**译自 POI 2014 Stage 2. Day 0「[Card](https://szkopul.edu.pl/problemset/problem/qpsk3ygf8MU7D_1Es0oc_xd8/site/?key=statement)」**
桌面上有依次排列的 $n$ 张卡片，每张卡片有正反两面。共 $m$ 次操作，每次操作会交换两张卡片，询问交换后是否有可能通过改变卡片的正反来使卡片上的数不降。
输入
第一行一个整数 $n$ ，表示卡片的数量。
接下来 $n$ 行，每行两个整数 $x_i,y_i$ ，表示卡片的正反两面。
接下来 $m$ 行，第 $j$ 行有两个整数 $a_j,b_j$，表示第 $j$ 次操作交换第 $a$ 张和 $b$ 张卡片。
输出
输出 $m$ 行，第 $j$ 行表示第 $j$ 次操作后是否能使卡片上的数不降，输出一行字符串 "TAK" 或 "NIE"，分别表示可能、不可能。
样例输入 复制
4
2 5
3 4
6 3
2 7
2
3 4
1 3样例输出 复制
NIE
TAK提示
数据范围：对于 $30\%$ 的数据，保证每张卡两面的数字相同。 对于 $38\%$ 的数据（可能不同），$n \le 2000$ 。 对于 $100\%$ 的数据， $2 \le n \le 200000 , 0 \le x_i,y_i \le 10^7 , 1 \le m \le 1000000$ 。 对于下发的三组样例： * 1ocen：$n=6,m=6$，用于测试程序正确性。 * 2ocen：$n=7,m=9$，保证卡的两面数字相同。 * 3ocen：$n=200000,m=1000000$，所有偶数编号的操作反转其前一次操作。