Nils is participating in the Canadian Cactus Competition (CCC)! Whilst the other competitors have brought their prized tall cacti, all dressed up with costumes and googly eyes, Nils has brought in something truly beautiful - a cactus graph!

The graph contains $N$ nodes labelled from $1$ to $N$, and $M$ edges. The $i$-th edge is bidirectional and connects nodes $u_i$ and $v_i$. Since the graph is a cactus, each edge belongs to at most one cycle.

Each of the nodes has a value, which is an integer between $0$ and $B$ (inclusive). Each edge has a colour equal to the bitwise XOR of the values of the nodes it connects. The beauty of the graph is the smallest colour of any edge in the graph.

The values of the nodes have not yet been finalised, so to boost his chances of winning first place, Nils wants to find the maximum possible beauty of the graph, and any possible allocation of values to nodes which achieves this beauty.

Constraints

$2\le N\le 2\times {10}^5$

$1\le M\le 3\times {10}^5$

$1\le u_i,v_i\le N,u_i\ne v_i$

There is at most one edge between any pair of nodes.

The graph is connected.

$1\le B\le {10}^9$

Subtask 1 [20%]

$B=1$

Subtask 2 [40%]

$B=2^k-1,k\in \mathbb{Z}$. That is, $B$ is one less than a power of two.

Subtask 3 [40%]

No additional constraints.

Input Specification

The first line of input contains three space-separated integers, $N,M,B$.

The $i$-th of the following $M$ lines of input contains two space-separated integers, $u_i,v_i$.

Output Specification

The first line of output should contain the maximum possible beauty of the graph.

The second line of output should contain $N$ space-separated integers, with the $i$-th integer representing the colour of the $i$-th node.

If there are multiple valid answers, output any of them.

Sample Input

4 4 2
1 2
2 3
1 3
3 4

Sample Output

1
0 1 2 0

Explanation

The first edge has a colour of $0\oplus 1=1$.

The second edge has a colour of $1\oplus 2=3$.

The third edge has a colour of $0\oplus 2=2$.

The fourth edge has a colour of $2\oplus 0=2$.

Here, $\oplus$ denotes the bitwise XOR operator.

Then, the beauty of the graph is $min(1,3,2,2)=1$. It can be shown that this is the maximum possible beauty.