CF1610F Mashtali: a Space Oddysey

Lee 计划接近 Mashtali 的内心，以推进他的邪恶计划（我们目前还不清楚具体内容），于是他决定美化 Mashtali 的图。但他为自己制定了若干规则。由于他太忙于自己的计划，没时间处理这些小事，所以他请你帮忙。 Mashtali 的图是一个无向带权图，有 $n$ 个顶点和 $m$ 条边，每条边的权值为 $1$ 或 $2$。Lee 想要给 Mashtali 的图定向，使其尽可能美丽。 Lee 认为有向带权图的美丽值等于其 Odyssey 顶点的数量。若顶点 $v$ 满足 $|d^+(v) - d^-(v)| = 1$，则称其为 Odyssey 顶点，其中 $d^+(v)$ 表示从 $v$ 出发的边的权值之和，$d^-(v)$ 表示指向 $v$ 的边的权值之和。 请你通过给 Mashtali 的图定向，使得图的美丽值最大，并给出一种实现方式。 注意，你必须为每条边定向。

第一行包含两个整数 $n$ 和 $m$，表示图的顶点数和边数，$1 \le n \le 10^5,\; 1 \le m \le 10^5$。 接下来的 $m$ 行中，第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $w_i$，表示第 $i$ 条边的两个端点和权值，$1 \le u_i, v_i \le n,\; u_i \neq v_i,\; w_i \in \{1, 2\}$。 注意，图不一定连通，且可能有重边。

第一行输出一个整数，表示 Lee 能获得的最大美丽值。 第二行输出一个长度为 $m$ 的字符串，表示每条边的定向方式。 如果你将第 $i$ 条边从 $u_i$ 指向 $v_i$，则第 $i$ 个字符应为 $1$；否则应为 $2$。

第一个样例的解释：  顶点 $2$ 和 $5$ 是 Odyssey 顶点。 第三个样例的解释：  顶点 $1$ 和 $6$ 是 Odyssey 顶点。 由 ChatGPT 4.1 翻译