P4258 [WC2016] Challenge NPC

Little N has recently been studying NP-complete problems. Seeing him so absorbed, Little O gave him such a problem: There are $n$ balls, numbered from $1$ to $n$. There are also $m$ baskets, numbered from $1$ to $m$. Each basket can hold at most $3$ balls. Each ball can only be placed into specific baskets. Specifically, there are $e$ constraints. The $i$-th constraint is described by two integers $v_i$ and $u_i$, meaning that ball $v_i$ can be placed into basket $u_i$. Every ball must be placed into some basket. If a basket contains at most $1$ ball, we call such a basket half-empty. Find the maximum possible number of half-empty baskets, and in an optimal arrangement, determine which basket each ball is placed into. Little N was stunned and lost his train of thought. Little I, watching from the side, chuckled, “Easy problem!” Then, with a few words, he described a polynomial-time algorithm. Little N was shocked. Three seconds later, he slapped the table: “No way! This problem is clearly NP-complete. Your algorithm must be wrong!” Little I smiled slightly: “Then I’ll wait for my Turing Award!” Little O can make problems but not solve them, so he turned to you—please investigate this problem and write a program to solve it.

In the input file $\tt{npc.in}$, the first line contains a single positive integer $T$, indicating there are $T$ test cases. For each test case, the first line contains three positive integers $n$, $m$, $e$, representing the number of balls, the number of baskets, and the number of constraints. The next $e$ lines each contain two integers $v_i$, $u_i$, indicating that ball $v_i$ can be placed into basket $u_i$.

The output file is $\tt{npc.out}$. For each test case, first output one line containing a single integer, the maximum possible number of half-empty baskets. Then output one more line containing $n$ integers $p_1, p_2, ... , p_n$, separated by spaces, describing one optimal arrangement. Here $p_i$ indicates that ball $i$ is placed into basket $p_i$. If there are multiple optimal solutions, any one of them may be printed.

For all testdata, $T \leq 5$, $1 \leq n \leq 3 m$. It is guaranteed that $1 \leq v_i \leq n$, $1 \leq u_i \leq m$, and there are no duplicate constraints. It is guaranteed that there exists at least one feasible solution in which every ball is placed into a basket and the number of balls in each basket does not exceed $3$. Each test point satisfies the following conventions: ::cute-table{tuack} |Test point|$ m $ |Notes | |:-:|:--------:|:--------:| |1 |$\leq 10$ |$n \leq 20, e \leq 25$| |2 |^ |^ | |3 |$\leq 100$|$e = n m$ | |4 |^ |There exists a solution with $m$ half-empty baskets.| |5 |^ |No solution has any half-empty basket.| |6 |^ |^ | |7 |^ |None | |8 |^ |^ | |9 |^ |^ | |10 |^ |^ | Translated by ChatGPT 5