P4258 [WC2016] 挑战NPC
题目描述
小 N 最近在研究 NP 完全问题，小 O 看小 N 研究得热火朝天，便给他出了一道这样的题目：
有 $n$ 个球，用整数 $1$ 到 $n$ 编号。还有 $m$ 个筐子，用整数 $1$ 到 $m$ 编号。每个筐子最多能装 $3$ 个球。
每个球只能放进特定的筐子中。 具体有 $e$ 个条件，第 $i$ 个条件用两个整数
$v_i$ 和 $u_i$ 描述，表示编号为 $v_i$ 的球可以放进编号为 $u_i$ 的筐子中。
每个球都必须放进一个筐子中。如果一个筐子内有不超过 $1$ 个球，那么我们称这样的筐子为半空的。
求半空的筐子最多有多少个，以及在最优方案中， 每个球分别放在哪个筐子中。
小 N 看到题目后瞬间没了思路，站在旁边看热闹的小 I 嘿嘿一笑：“水题！”
然后三言两语道出了一个多项式算法。
小 N 瞬间就惊呆了，三秒钟后他回过神来一拍桌子：“不对！这个问题显然是 NP 完全问题，你算法肯定有错！”
小 I 浅笑：“所以，等我领图灵奖吧！”
小 O 只会出题不会做题，所以找到了你——请你对这个问题进行探究，并写一个程序解决此题。
输入格式
无
输出格式
无
说明/提示
对于所有数据， $T \leq 5, 1 \leq n \leq 3m$。 保证 $1 \leq v_i \leq n, 1 \leq u_i \leq m$，且不会出现重复的条件。
保证至少有一种合法方案，使得每个球都放进了筐子，且每个筐子内球的个
数不超过 $3$。
各测试点满足以下约定：
