← 返回题目列表

Codeforces · 1610/F

F. 马什塔利:太空漫游

中文机器翻译题面 查看原题

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。