A1476. 手套
问题描述
有两位医生和两位病人,每位医生需要为每位病人做一场手术。为了避免医生的手直接接触到病人,医生在手术中必须佩带手套。然而,手套被使用后,内表面会沾染医生的汗液,外表面会沾染病人的血液。医生和病人都不愿意接触到其他人的汗液或血液。现在,只有两副手套,如何完成这四场手术?
使用传统的方法,是不可能通过两副手套完成四场手术的。于是,我们想到了一个神奇的方法——将两副手套套在一起!但是,将手套套在一起可能导致接触面的损坏。根据多年的临床经验总结,只有两副手套的接触面均为全新(没有任何汗液和血液且没有被损坏过)的情况下,才不会导致接触面损坏,否则接触的两个表面均会被损坏。若一副手套的某个表面被损坏过,则医生和病人都不再愿意接触该表面。在尝试了各种方法后,我们得到了下面的解决方案:
步骤一:医生0给病人0做手术,使用手套b套手套a(手套b在外面)
步骤二:医生0给病人1做手术,使用手套a
步骤三:医生1给病人0做手术,使用手套b
步骤四:医生1给病人1做手术,使用手套a套手套b(手套a在外面)
显然,佩戴过多的手套会影响手术质量,所以我们规定一场手术中最多使用两副手套套在一起。现在,我们有n位医生,m位病人,其中某些医生需要给某些病人做手术。请你帮忙计算,最少使用多少副手套可以完成所有手术?
值得注意的是:一副手套被当做一个整体,不可以拆成“两只”分别使用。此外,如果有必要,手套是可以“翻过来”使用的。
使用传统的方法,是不可能通过两副手套完成四场手术的。于是,我们想到了一个神奇的方法——将两副手套套在一起!但是,将手套套在一起可能导致接触面的损坏。根据多年的临床经验总结,只有两副手套的接触面均为全新(没有任何汗液和血液且没有被损坏过)的情况下,才不会导致接触面损坏,否则接触的两个表面均会被损坏。若一副手套的某个表面被损坏过,则医生和病人都不再愿意接触该表面。在尝试了各种方法后,我们得到了下面的解决方案:
步骤一:医生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号病人需要做一场手术。数据保证不会出现两场相同的手术。
对于每组测试数据:第一行有三个正整数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副手套的编号(字母),并用空格分隔。特别地。若某副手套在该次手术中是以“翻过来”的状态使用的,则用对应的大写字母来表示,否则用小写字母表示,详见样例。
对于每一组答案:第一行包含一个正整数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 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
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
数据规模和约定
测试点编号 | n | m | s | T |
1 | n ≤ 3 | m ≤ 3 | s ≤ n*m | T ≤ 10 |
2 | n =1 | m ≤ 10 | ||
3 | n ≤ 4 | m ≤ 4 | ||
4 | n ≤ 6 | m ≤ 6 | ||
5 | n ≤ 6 | m ≤ 10 | ||
6 | n ≤ 7 | m ≤ 7 | ||
7 | n ≤ 8 | m ≤ 8 | ||
8 | n ≤ 9 | m ≤ 9 | ||
9 | n ≤ 9 | m ≤ 10 | ||
10 | n ≤ 10 | m ≤ 10 |