E. XORradas
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$, $$$k$$$, and a list $$$a$$$ of non-negative integers of length $$$2n$$$, where each element is greater than or equal to $$$k$$$ ($$$a_i \ge k$$$ for all $$$i$$$).

Find a minimum-size partition$$$^\dag$$$ of $$$a$$$ that satisfies the following condition:

  • The $$$\mathsf{XOR}^\ddag$$$ of the elements in each part of the partition is greater than or equal to $$$k$$$.

$$$^\dag$$$ A partition of $$$a$$$ into $$$s$$$ parts is represented by assigning each element of $$$a$$$ to an integer between $$$1$$$ and $$$s$$$, so that elements assigned to the same integer belong to the same part. We say that $$$s$$$ is the size of the partition.

$$$^\ddag$$$ The bitwise $$$\mathsf{XOR}$$$ operation of two non-negative integers is calculated as follows:

The two numbers are written in binary, and the result is the number written in binary that has 1 in positions where the operands have different values, and 0 in positions where the operands have the same value, for example $$$10 \, \mathsf{XOR} \, 12 = 6$$$, since $$$10 = 1010_2$$$, $$$12 = 1100_2$$$, and $$$6 = 0110_2$$$.

To calculate the $$$\mathsf{XOR}$$$ operation of multiple integers $$$x_1, \ldots, x_n$$$, the following expression is evaluated: $$$(( \dots ((x_1 \, \mathsf{XOR} \, x_2) \, \mathsf{XOR} \, x_3 ) \dots ) \, \mathsf{XOR} \, x_n)$$$.

If a part has only one element, the $$$\mathsf{XOR}$$$ of all elements in the part is equal to that same number.

Input

The first line of the input contains the number of cases $$$T$$$.

For each case, there will be a line of input with two integers $$$n$$$, $$$k$$$.

The next line for each case contains $$$2n$$$ non-negative integers $$$a_1, \ldots, a_{2n}$$$.

Output

For each case, you should print a line with an integer $$$s$$$, the minimum size of the partition.

Next, you should print a line with $$$2n$$$ values between $$$1$$$ and $$$s$$$, representing the partition. (If the $$$i$$$-th value is $$$j$$$, it means that $$$a_i$$$ belongs to the $$$j$$$-th part).

Scoring
  1. (23 points) The sum of $$$2n$$$ for all cases is at most $$$6$$$.
  2. (28 points) The sum of $$$2n$$$ for all cases is at most $$$24$$$.
  3. (37 points) The sum of $$$2n$$$ for all cases is at most $$$2 \cdot 10^5$$$.
  4. (12 points) No additional restrictions.
Example
Input
2
2 1
1 3 4 1
2 1
2 1 2 1
Output
1
1 1 1 1
2
1 1 2 2
Note

$$$1 \le T \le 10^6$$$.

$$$1 \le n \le 2 \cdot 10^6$$$.

The sum of $$$n$$$ for all cases is at most $$$2 \cdot 10^6$$$.

$$$0 \le k \le a_i \le 10^{18}$$$.