#P3526. [Poi2014]Card
[Poi2014]Card
[POI2014] Cards
题目描述
桌上从左到右排着 张卡片,每张卡片的正面和反面各写有一个数。开始时所有卡片都正面朝上。魔术师 Bajtazar 要让卡片上可见的数字从左到右不下降,为此他可以翻转任意若干张卡片。
每次有一名观众交换两张卡片的位置。他们的交换依次发生。请在每次交换后判断,当前顺序下能否通过翻转卡片使可见数字不下降。判断时可以独立选择每张卡片哪一面朝上,不能改变卡片顺序。初始顺序不必满足要求。
输入格式
第一行一个整数 。随后 行,每行两个整数 ,表示初始位于第 个位置的卡片正面、反面的数字。
接下来一行一个整数 。随后 行,每行两个整数 ,表示交换当前位于这两个位置的卡片。位置从左到右从 开始编号。
输出格式
输出 行。在第 行,若第 次交换后可以实现要求,输出 TAK。否则输出 NIE。
样例 #1
4
2 5
3 4
6 3
2 7
2
3 4
1 3
NIE
TAK
第一次交换后,从第二张卡片起可见值至少为 ,第三张只能选 ,最后一张没有大于或等于 的一面。第二次交换后,翻转第三张卡片即可得到 。
数据范围
,,,。
原赛有 的分值满足每张卡片两面的数字相同,另有 的分值满足 ,两类测试可重叠。
原赛公开评测用例包括 的小规模测试、 且每张卡片两面相同的测试,以及 且每次偶数编号交换都会还原上一次交换的测试。