Description:


小 N 最近在研究 NP 完全问题,小 O 看小 N 研究得热火朝天,便给他出了一道这样的题目:
有 n 个球,用整数 1 到 n 编号。还有 m 个筐子,用整数 1 到 m 编号。
每个筐子最多能装 3 个球。
每个球只能放进特定的筐子中。具体有 e 个条件,第 i 个条件用两个整数 vi 和 ui 描述,表示编号为 vi 的球可以放进编号为 ui 的筐子中。
每个球都必须放进一个筐子中。如果一个筐子内有不超过 1 个球,那么我们称这样的筐子为半空的。
求半空的筐子最多有多少个,以及在最优方案中,每个球分别放在哪个筐子中。
小 N 看到题目后瞬间没了思路,站在旁边看热闹的小 I 嘿嘿一笑:“水题!”
然后三言两语道出了一个多项式算法。
小 N 瞬间就惊呆了,三秒钟后他回过神来一拍桌子:
“不对!这个问题显然是 NP 完全问题,你算法肯定有错!”
小 I 浅笑:“所以,等我领图灵奖吧!”
小 O 只会出题不会做题,所以找到了你——请你对这个问题进行探究,并写一个程序解决此题。

Input:


第一行包含 1 个正整数 T,表示有 T 组数据。
对于每组数据,第一行包含 3 个正整数 n,m,e,表示球的个数,筐子的个数和条件的个数。
接下来 e 行,每行包含 2 个整数 vi,ui,表示编号为 vi 的球可以放进编号为 ui 的筐子。

Output:


对于每组数据,先输出一行,包含一个整数,表示半空的筐子最多有多少个。
然后再输出一行,包含 n 个整数 p1,p2,…,pn,相邻整数之间用空格隔开,表示一种最优解。其中 pi 表示编号为 i 的球放进了编号为 pi 的筐子。如果有多种最优解,可以输出其中任何一种。

Sample Input:


Sample Output:


题解:


这个题十分的巧妙,据说去年wc现场没有一个人做出来。
我们把每个筐拆成三个点,互相连线(不全部连上也可以),然后若某个球可以放进该筐,则与这三个点连线。
整个图的最大匹配数减去n就得到了答案。
因为对于每一个筐,若没有一个点被匹配,则自己可以有一个匹配,若被匹配了一个点,剩下的两个点也匹配了,正好满足半空的筐的计数性质。这就是此题的巧妙之处。
一般图匹配要用到带花树算法: 戳我(^_^)
膜一膜出题人VFK Orz Orz Orz

代码如下,感谢段爷爷的帮助(^_^) :