2147. [WC 2016] 挑战NPC

【题目描述】

小 $N$ 最近在研究 $NP$ 完全问题，小 $O$ 看小 $N$ 研究得热火朝天，便给他出了一道这样的题目：

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

【输入格式】

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

【输出格式】

对于每组数据，先输出一行，包含一个整数，表示半空的筐子最多有多少个。

然后再输出一行，包含 $n$ 个整数 $p_1,p_2,...,p_n$，相邻整数之间用空格隔开，表示一种最优解。其中 $p_i$ 表示编号为 $i$ 的球放进了编号为 $p_i$ 的筐子。如果有多种最优解，可以输出其中任何一种。

【样例输入】

1
4 3 6
1 1
2 1
2 2
3 2
3 3
4 3

【样例输出】

2
1 2 3 3

【提示】