#P18601. Job for a Hobbit
Job for a Hobbit
Job for a Hobbit
题目描述
黑巫师 Byteon 也从魔戒中汲取力量,但他不愿像 Sauron 那样把命运寄托在一枚小小的戒指上。在黑塔前,一排 根魔法杆上各套着恰好 枚彩色魔戒。
善良的巫师 Bitalf 预言:Byteon 的力量来自多样性,如果每根杆上至多只有一种颜色的魔戒,或根本没有魔戒,他就会失去力量。
Bitalf 不想亲自搬动魔戒,于是在原来这一排杆的左右两端各变出一根空杆。现在共有 根杆,编号为 ,最初杆 为空,中间的每根杆仍有 枚戒指。
搬运任务交给了霍比特人 Bitbo Byteins。每天,他可以把一根杆的最顶端一枚戒指取下,放到一根相邻杆的顶端。任意时刻,每根杆上都不能超过 枚戒指。
请给出一个不超过 步的方案,使所有 根杆最终都至多包含一种颜色的戒指(允许空杆),或判断无法做到。
输入格式
第一行一个整数 ,表示测试用例数,。
每个测试用例第一行两个整数 ,满足 、。
接下来 行,每行 个整数 ,表示第 根杆上的戒指颜色,按从底部到顶部的顺序给出,。
杆 最初为空,不在输入中另列。
所有测试用例的 之和不超过 。
输出格式
对每个测试用例,若无解,输出一行 NIE。
否则输出一行 TAK,下一行输出移动次数 ,。接下来 行,每行两个整数 ,表示把杆 顶端的戒指移到杆 顶端。
每一步都必须满足:
- ,且 ;
- 移动前杆 非空;
- 移动前杆 上少于 枚戒指。
最终每根杆至多含一种颜色。多种合法方案中输出任意一种,只要步数不超过上限。
样例输入 1
2
2 2
1 2
2 1
1 4
1 2 3 4
样例输出 1
TAK
2
1 0
2 1
NIE