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$$$ 传入的边的权重之和。
通过引导 Mashtali 图的边,找到 Lee 可以实现的图的最大可能美感。此外,想办法实现它。
请注意,您必须确定每个边缘的方向。
输入
第一行包含两个整数 $$$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$$$ 条边的端点及其权重。
请注意,该图不必是连接的,并且它可能包含多个边。
输出
在第一行打印一个整数——Lee 可以实现的图表的最大美感。
在第二行中打印一个长度为 $$$m$$$ 的字符串,其中包含 $$$1$$$s 和 $$$2$$$s — 边缘的方向。
如果您决定将第 $$$i$$$ 条边从顶点 $$$u_i$$$ 定向到顶点 $$$v_i$$$,则字符串的第 $$$i$$$ 字符应为 $$$1$$$。否则,它应该是$$$2$$$。
示例
输入 #1
6 7 1 2 1 1 3 2 2 3 2 1 4 1 4 5 1 2 5 2 2 6 2
输出 #1
2 1212212
输入 #2
6 7 1 2 2 1 3 2 2 3 2 1 4 2 4 5 2 2 5 2 2 6 2
输出 #2
0 1212212
输入 #3
6 7 1 2 1 1 3 1 2 3 1 1 4 1 4 5 1 2 5 1 2 6 1
输出 #3
2 1212212
注意
第一个样本的说明:
顶点 $$$2$$$ 和 $$$5$$$ 是 Oddysey。
第三个样本的说明:
顶点 $$$1$$$ 和 $$$6$$$ 是 Oddysey。