[Ctsc2013]手套

时间限制:100s      空间限制:256MB

题目描述

有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
224
01 00 10 11
323
01 10 21

样例输出

2
1 2 a b
0 1 a 
2 1 b

提示

T<=10 N<=10 M<=10 S<=N*M


题目来源

vfleaking提供spj

Menuappsclose