Mashtali: a Space Oddysey

给定一张含 $n$ 个点 $m$ 条边的无向图，结点编号为 $1$ 到 $n$。 每条边有边权 $w_i$，而 $w_i$ 只能等于 $1$ 或 $2$。蓝想要给每条边定向，使得图尽可能的可爱。 图的可爱程度定义为图中好的结点的数量。一个结点 $v$ 是好的，当且仅当令 $d^+(v)$ 为 $v$ 所有出边的权值和，令 $d^-(v)$ 为 $v$ 所有入边的权值和，有 $|d^+(x)-d^-(x)|=1$。 试着帮蓝找到图的最大可能可爱程度，并且给出任意一种构造方案。 输入中，蓝会在第一行给出 $n$ 和 $m$，之后 $m$ 行每行依次给出 $u_i,v_i$ 和 $w_i$，其中前两个数代表边 $i$ 连接的两个结点，而 $w_i$ 则代表边 $i$ 的边权。 输出中，在第一行，你应该输出图的最大可能可爱程度。在输出的第二行，为了告诉蓝你的构造方案，你需要给出一个字符串 $s$，其中若 $s_i=1$，则代表边 $i$ 被定向为从 $u_i$ 到 $v_i$，而 $s_i=2$ 则代表边 $i$ 被定向为从 $v_i$ 到 $u_i$。 本题数据满足：$1 \leq n,m \leq 3\times10^5，1 \leq u_i,v_i \leq n，\mathbf{w_i\in\{1,2\}}$。

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.

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.

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 $ .

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

2
1212212

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

0
1212212

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

2
1212212

Explanation for the first sample: vertices $ 2 $ and $ 5 $ are Oddyseys.Explanation for the third sample: vertices $ 1 $ and $ 6 $ are Oddyseys.