Little N has recently been studying NP-complete problems. Seeing Little N working with great enthusiasm, Little O posed the following problem to him:

There are $n$ balls, numbered $1$ to $n$. There are also $m$ baskets, numbered $1$ to $m$. Each basket can hold at most $3$ balls.

Each ball can only be placed into specific baskets. Specifically, there are $e$ conditions, where the $i$-th condition is described by two integers $v_i$ and $u_i$, indicating that the ball numbered $v_i$ can be placed into the basket numbered $u_i$.

Every ball must be placed into a basket. If a basket contains no more than $1$ ball, we call such a basket "half-empty."

Find the maximum number of half-empty baskets, and in an optimal configuration, which basket each ball is placed into.

After seeing the problem, Little N was instantly stumped. Little I, who was watching from the side, chuckled and said, "Easy problem!" and proceeded to describe a polynomial-time algorithm in a few words.

Little N was stunned. Three seconds later, he came to his senses and slammed the table: "No! This problem is clearly NP-complete; your algorithm must be wrong!"

Little I smiled: "Well then, wait for me to receive the Turing Award!"

Little O only knows how to pose problems, not how to solve them, so he found you—please investigate this problem and write a program to solve it.

Input

The first line contains a single positive integer $T$, representing the number of 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 conditions, respectively.

The next $e$ lines each contain two integers $v_i, u_i$, indicating that the ball numbered $v_i$ can be placed into the basket numbered $u_i$.

Output

For each test case, first output a single line containing an integer, representing the maximum number of half-empty baskets.

Then, output another line containing $n$ integers $p_1, p_2, \dots, p_n$, separated by spaces, representing an optimal solution. Here, $p_i$ indicates that the ball numbered $i$ is placed into the basket numbered $p_i$. If there are multiple optimal solutions, you may output any one of them.

Examples

Input 1

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

Output 1

2
1 2 3 3

Input 2

See npc/npc.in and npc/npc.ans in the contestant directory.

Constraints

For all data, $T \le 5$, $1 \le n \le 3m$. It is guaranteed that $1 \le v_i \le n$, $1 \le u_i \le m$, and no duplicate conditions will appear.

It is guaranteed that there is at least one valid configuration where every ball is placed into a basket and each basket contains no more than $3$ balls.

The test cases satisfy the following conditions: