CF1610F.Mashtali: a Space Oddysey

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 $1$ or $2$. 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 $|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.

Lee 为了推进其邪恶计划（我们目前尚不清楚具体内容），打算拉近与 Mashtali 的关系，因此决定美化 Mashtali 的图。但他为自己设定了若干规则。此外，由于他正忙于筹划，无暇顾及此类琐事，于是请求你帮忙。

Mashtali 的图是一个含 $n$ 个顶点、$m$ 条边的无向带权图，每条边的权重为 $1$ 或 $2$。Lee 希望将 Mashtali 图中的每条边定向，使其尽可能“美丽”。

Lee 认为一个有向带权图的“美丽值”等于其 Oddysey 顶点 的数量。顶点 $v$ 被称为 Oddysey 顶点，当且仅当 $|d^+(v) - d^-(v)| = 1$，其中 $d^+(v)$ 表示从 $v$ 出发的所有出边的权重之和，$d^-(v)$ 表示所有指向 $v$ 的入边的权重之和。

请找出 Lee 通过对 Mashtali 图的边进行定向所能达到的最大美丽值，并给出一种达到该最大值的具体定向方案。

注意：你必须对每条边都指定方向。

The first line contains two integers $n$ and $m$ $(1 \le n \le 10^5;\; 1 \le m \le 10^5)$ — the numbers of vertices and edges in the graph.

The $i$-th line of the following $m$ lines contains three integers $u_i$, $v_i$ and $w_i$ $( 1 \le u_i , v_i \le n;\; u_i \neq v_i;\; \bf{w_i \in {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.

第一行包含两个整数 $n$ 和 $m$ $(1 \le n \le 10^5;\; 1 \le m \le 10^5)$ —— 分别表示图中顶点和边的数量。

接下来的 $m$ 行中，第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $w_i$ $( 1 \le u_i , v_i \le n;\; u_i \neq v_i;\; \bf{w_i \in {1, 2}} )$ —— 分别表示第 $i$ 条边的两个端点及其权重。

注意：该图未必连通，且可能包含重边。

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 $1$s and $2$s — directions of the edges.

If you decide to direct the $i$-th edge from vertex $u_i$ to vertex $v_i$, $i$-th character of the string should be $1$. Otherwise, it should be $2$.

第一行输出一个整数——Lee 能达到的最大图的美观度。

第二行输出一个长度为 $m$ 的字符串，仅由字符 $1$ 和 $2$ 组成——表示各条边的方向。

若你决定将第 $i$ 条边从顶点 $u_i$ 指向顶点 $v_i$，则该字符串的第 $i$ 个字符应为 $1$；否则应为 $2$。

Explanation for the first sample:

vertices $2$ and $5$ are Oddyseys.

Explanation for the third sample:

vertices $1$ and $6$ are Oddyseys.

第一个样例的解释：

顶点 $2$ 和 $5$ 是奥德赛点（Oddyseys）。

第三个样例的解释：

顶点 $1$ 和 $6$ 是奥德赛点（Oddyseys）。