Mashtali: a Space Oddysey solution codeforces

Table of Contents

Mashtali: a Space Oddysey solution codeforces

Lee was planning to get closer to Mashtali’s heart to proceed with his evil plan(which we’re not aware of, yet), so he decided to beautify Mashtali’s graph. But he made several rules for himself. And also he was too busy with his plans that he didn’t have time for such minor tasks, so he asked you for help.

Mashtali’s graph is an undirected weighted graph with 𝑛n vertices and 𝑚m edges with weights equal to either 11 or 22. Lee wants to direct the edges of Mashtali’s graph so that it will be as beautiful as possible.

Lee thinks that the beauty of a directed weighted graph is equal to the number of its Oddysey vertices. A vertex 𝑣v is an Oddysey vertex if |𝑑+(𝑣)𝑑(𝑣)|=1|d+(v)−d−(v)|=1, where 𝑑+(𝑣)d+(v) is the sum of weights of the outgoing from 𝑣v edges, and 𝑑(𝑣)d−(v) is the sum of the weights of the incoming to 𝑣v edges.

Find the largest possible beauty of a graph that Lee can achieve by directing the edges of Mashtali’s graph. In addition, find any way to achieve it.

Note that you have to orient each edge.

Mashtali: a Space Oddysey solution codeforces Input

The first line contains two integers 𝑛n and 𝑚m (1𝑛3105;1𝑚3105)(1≤n≤3⋅105;1≤m≤3⋅105) — the numbers of vertices and edges in the graph.

The 𝑖i-th line of the following 𝑚m lines contains three integers 𝑢𝑖ui𝑣𝑖vi and 𝑤𝑖wi (1𝑢𝑖,𝑣𝑖𝑛;𝑢𝑖𝑣𝑖;𝐰𝐢{1,2})(1≤ui,vi≤n;ui≠vi;wi∈{1,2}) — the endpoints of the 𝑖i-th edge and its weight.

Note that the graph doesn’t have to be connected, and it might contain multiple edges.

Output

In the first line print a single integer — the maximum beauty of the graph Lee can achieve.

In the second line print a string of length 𝑚m consisting of 11s and 22s — directions of the edges.

If you decide to direct the 𝑖i-th edge from vertex 𝑢𝑖ui to vertex 𝑣𝑖vi𝑖i-th character of the string should be 11. Otherwise, it should be 22.

Examples
input

Copy Mashtali: a Space Oddysey solution codeforces

6 7
1 2 1
1 3 2
2 3 2
1 4 1
4 5 1
2 5 2
2 6 2

output

Copy
2
1212212

input

Copy
6 7
1 2 2
1 3 2
2 3 2
1 4 2
4 5 2
2 5 2
2 6 2

output

Copy
0
1212212

input

Copy
6 7
1 2 1
1 3 1
2 3 1
1 4 1
4 5 1
2 5 1
2 6 1


output Mashtali: a Space Oddysey solution codeforces

2
1212212

Note

Explanation for the first sample:

vertices 22 and 55 are Oddyseys.
Explanation for the third sample:

vertices 11 and 66 are Oddyseys.