#2845. [NOIP2022] 喵了个喵

[NOIP2022] 喵了个喵

题目描述

小 E 喜欢上了一款叫做《喵了个喵》的游戏。这个游戏有一个牌堆和 nn 个可以从栈底删除元素的栈,任务是要通过游戏规则将所有的卡牌消去。开始时牌堆中有 mm 张卡牌,从上到下的图案分别是 a1,a2,,ama_1, a_2,\dots, a_m。所有的卡牌一共有 kk 种图案,从 11kk 编号。牌堆中每一种图案的卡牌都有偶数张。开始时所有的栈都是空的。这个游戏有两种操作:

  • 选择一个栈,将牌堆顶上的卡牌放入栈的顶部。如果这么操作后,这个栈最上方的两张牌有相同的图案,则会自动将这两张牌消去。
  • 选择两个不同的栈,如果这两个栈栈的卡牌有相同的图案,则可以将这两张牌消去,原来在栈底上方的卡牌会成为新的栈底。如果不同,则什么也不会做。

这个游戏一共有 TT 关,小 E 一直无法通关。请你帮小 E 设计一下游戏方案,即对于游戏的每一关,给出相应的操作序列使得小 E 可以把所有的卡牌消去。

输入格式

第一行包含一个正整数 TT,表示数据组数。

接下来一共 TT 组数据,在每组数据中:

第一行包含三个正整数 n,m,kn, m, k,分别表示栈的个数、卡牌的个数、卡牌上图案的种类。

第二行包含 mm 个正整数,分别表示 a1,a2,,ama_1, a_2,\dots, a_m,分别从上到下表示牌堆中卡牌的图案。

输入数据保证有解。

输出格式

对于每一组数据,输出若干行。

其中第一行包含一个正整数 op\mathrm{op},表示操作的次数。你需要保证 mop2×mm \leq \mathrm{op} \leq 2\times m

接下来 op\mathrm{op} 行,每行包含两个或三个正整数,整数之间用一个空格隔开。

若为两个整数 1 s\texttt{1 s},则进行一次第一个操作并选择栈 ss

若为三个整数 2 s1 s2\texttt{2 s1 s2},则进行一次第二个操作并选择栈 s1s_1s2s_2

你需要保证 1s,s1,s2n1 \leq s, s_1, s_2 \leq n,且 s1s2s_1 \neq s_2

样例 #1

样例输入 #1

1
2 4 2
1 2 1 2

样例输出 #1

5
1 1
1 1
1 2
2 1 2
1 1

提示

【样例 1 解释】

下图是初始状态。

下图是前两次操作之后的结果。

下图是第三次和第四次操作之后的结果。

下图是第五次操作之后的结果。

【样例 2】

见选手目录下的 meow/meow2.in\texttt{meow/meow2.in}meow/meow2.ans\texttt{meow/meow2.ans}

【数据范围】

SS 为所有 TT 组数据中 mm 的总和。

对于所有数据,保证 S2×106S \leq 2 \times 10^61n3001 \leq n \leq 3001aik1 \leq a_i \leq k

测试点 T=T= nn k=k= mm \leq
131\sim 3 10011001 300\leq 300 2n22n-2 无限制
464\sim 6 10021002 =2=2 2n12n-1
7107\sim 10 33 =3=3 1414
111411\sim 14 10041004 无限制
152015\sim 20 10051005 300\leq 300

【评分方式】

对于每一组数据,若在按顺序进行所有操作后,牌堆为空且所有的栈均为空,则认为你的答案正确。

【提示】

你可以通过 TT 的个位数来判断这个测试点是属于哪一类数据。

你的输出不需要与样例输出一致,输出任意一个合法解即可得分。