#2466. 「POI2014」卡片 Card

内存限制:64 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

译自 POI 2014 Stage 2. Day 0「Card

桌面上有依次排列的 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 ,所有偶数编号的操作反转其前一次操作。