暂无测试数据。

题目描述

有两位医生和两位病人，
每位医生需要为每位病人做一场手术。
为了避免医生的手直接接触到病人，
医生在手术中必须佩带手套。

然而，
手套被使用后，
内表面会沾染医生的汗液，
外表面会沾染病人的血液。
医生和病人都不愿意接触到其他人的汗液或血液。

现在，
只有两副手套，
如何完成这四场手术？

使用传统的方法，
是不可能通过两副手套完成四场手术的。
于是，
我们想到了一个神奇的方法——将两副手套套在一起！
但是，
将手套套在一起可能导致接触面的损坏。
根据多年的临床经验总结，
只有两副手套的接触面均为全新（没有任何汗液和血液且没有被损坏过）的情况下，
才不会导致接触面损坏，
否则接触的两个表面均会被损坏。

若一副手套的某个表面被损坏过，
则医生和病人都不再愿意接触该表面。
在尝试了各种方法后，
我们得到了下面的解决方案：

步骤一：医生 0 给病人 0 做手术，
使用手套 b 套手套 a （手套b在外面）

步骤二：医生 0 给病人 1 做手术，
使用手套 a

步骤三：医生 1 给病人 0 做手术，
使用手套 b

步骤四：医生 1 给病人 1 做手术，
使用手套 a 套手套 b（手套 a 在外面）
显然，
佩戴过多的手套会影响手术质量，
所以我们规定一场手术中最多使用两副手套套在一起。

现在，
我们有 \(n\) 位医生，
\(m\) 位病人，
其中某些医生需要给某些病人做手术。
请你帮忙计算，
最少使用多少副手套可以完成所有手术？
值得注意的是：
一副手套被当做一个整体，
不可以拆成“两只”分别使用。
此外，
如果有必要，
手套是可以“翻过来”使用的。

输入

第一行，包含一个正整数 \(T\)，
表示该文件中含有 \(T\) 组测试数据。

对于每组测试数据：
第一行，有三个正整数 \(n,m,s\)。
表示有 \(n\) 位医生（编号 0 至 \(n-1\)），
有 \(m\) 位病人（编号 0 至 \(m-1\)），
有 \(s\) 场手术（编号 0 至 \(s-1\)）。
随后 \(s\) 行，
按编号顺序描述每一场手术。
每行有两个非负整数 \(x\)、\(y\)，
表示 \(x\) 号医生和 \(y\)号病人需要做一场手术。
数据保证不会出现两场相同的手术。

输出

应包含 \(T\) 组测试数据的答案。

对于每一组答案：
第一行包含一个正整数 \(p\)，
表示你需要使用 \(p\) 副手套（从字母 \(a\) 开始顺序编号）。
随后 \(s\) 行，
你需要按时间顺序描述每场手术安排，
每场手术单独使用一行。
对于一场手术，
你需要先输出它的编号，
随后输出它使用的手套数量 \(k\)（必须是1或2），
接下来以自内向外（从医生向病人）的顺序输出所使用的 \(k\) 副手套的编号（字母），
并用空格分隔。
特别地。
若某副手套在该次手术中是以“翻过来”的状态使用的，
则用对应的大写字母来表示，
否则用小写字母表示，
详见样例。

样例输入

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

样例输出

2
1 2 a b
0 1 a
2 1 b
3 2 b a
3
0 2 a b
1 2 A B
2 1 c

数据范围限制

限制

每个测试点时限：10秒
内存限制：256MB