#P18601. Job for a Hobbit

Job for a Hobbit

Job for a Hobbit

题目描述

黑巫师 Byteon 也从魔戒中汲取力量,但他不愿像 Sauron 那样把命运寄托在一枚小小的戒指上。在黑塔前,一排 nn 根魔法杆上各套着恰好 kk 枚彩色魔戒。

善良的巫师 Bitalf 预言:Byteon 的力量来自多样性,如果每根杆上至多只有一种颜色的魔戒,或根本没有魔戒,他就会失去力量。

Bitalf 不想亲自搬动魔戒,于是在原来这一排杆的左右两端各变出一根空杆。现在共有 n+2n+2 根杆,编号为 0,1,…,n+10,1,\ldots,n+1,最初杆 0,n+10,n+1 为空,中间的每根杆仍有 kk 枚戒指。

搬运任务交给了霍比特人 Bitbo Byteins。每天,他可以把一根杆的最顶端一枚戒指取下,放到一根相邻杆的顶端。任意时刻,每根杆上都不能超过 kk 枚戒指。

请给出一个不超过 10000001000000 步的方案,使所有 n+2n+2 根杆最终都至多包含一种颜色的戒指(允许空杆),或判断无法做到。

输入格式

第一行一个整数 zz,表示测试用例数,1≤z≤251\le z\le25。

每个测试用例第一行两个整数 n,kn,k,满足 1≤n≤501\le n\le50、1≤k≤101\le k\le10。

接下来 nn 行,每行 kk 个整数 ai1,…,aika_{i1},\ldots,a_{ik},表示第 ii 根杆上的戒指颜色,按从底部到顶部的顺序给出,0≤aij≤1090\le a_{ij}\le10^9。

杆 0,n+10,n+1 最初为空,不在输入中另列。

所有测试用例的 nn 之和不超过 5050。

输出格式

对每个测试用例,若无解,输出一行 NIE。

否则输出一行 TAK,下一行输出移动次数 pp,0≤p≤10000000\le p\le1000000。接下来 pp 行,每行两个整数 ui,viu_i,v_i,表示把杆 uiu_i 顶端的戒指移到杆 viv_i 顶端。

每一步都必须满足:

  • 0≤ui,vi≤n+10\le u_i,v_i\le n+1,且 ∣ui−vi∣=1|u_i-v_i|=1;
  • 移动前杆 uiu_i 非空;
  • 移动前杆 viv_i 上少于 kk 枚戒指。

最终每根杆至多含一种颜色。多种合法方案中输出任意一种,只要步数不超过上限。

样例输入 1

2
2 2
1 2
2 1
1 4
1 2 3 4

样例输出 1

TAK
2
1 0
2 1
NIE