CF1407E Egor in the Republic of Dagestan

Egor 是一位著名的俄罗斯歌手、说唱歌手、演员和博主，终于他决定在阳光明媚的达吉斯坦共和国举办一场演唱会。 该共和国有 $n$ 个城市，其中一些城市之间通过 $m$ 条有向道路相连，没有其他附加条件。换句话说，达吉斯坦的道路系统可以表示为一个任意的有向图。Egor 将抵达城市 $1$，沿着某条道路路径前往城市 $n$，举办演唱会后离开。 作为一位著名艺人，Egor 有许多黑粉和过于热情的粉丝，因此他只能通过安全的道路旅行。达吉斯坦的道路分为两种类型：黑色和白色。黑色道路仅在夜间安全，白色道路仅在早晨安全。在出发前，Egor 的经纪人会为每个城市指定一种颜色（黑色或白色），然后在旅途中，如果他们到达某个城市，只有在该城市颜色对应的时间（黑色为夜间，白色为早晨）才能离开该城市。制定好计划后，Egor 会选择一条从 $1$ 到 $n$ 的可用路径，并且出于安全考虑，这条路径必须是最短的。 Egor 的经纪人非常喜欢达吉斯坦，希望能在这里多待一段时间，因此他希望你制定一个计划，使得不存在从 $1$ 到 $n$ 的路径，或者最短路径的长度尽可能大。 一条路径是指一个城市或一系列道路，使得每条道路（除第一条外）出发的城市等于前一条道路到达的城市。Egor 只能沿着由安全道路组成的路径移动。 路径的长度等于其中道路的数量。图中的最短路径是指长度最小的路径。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 500000$，$0 \leq m \leq 500000$），分别表示城市数量和道路数量。 接下来的 $m$ 行中，第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $t_i$（$1 \leq u_i, v_i \leq n$，$t_i \in \{0, 1\}$），表示一条连接城市的道路及其类型（$0$ 表示夜间道路，$1$ 表示早晨道路）。

第一行输出所需路径的长度（如果可以选择一种方案使得不存在从 $1$ 到 $n$ 的路径，则输出 $-1$）。 第二行输出所需的计划——一个长度为 $n$ 的字符串，第 $i$ 位为 $0$ 表示第 $i$ 个城市为夜间城市，为 $1$ 表示为早晨城市。 如果有多种答案，输出任意一种即可。

对于第一个样例，如果我们将城市 $1$ 涂成白色，最短路径为 $1 \rightarrow 3$。否则，无论其他城市如何着色，最短路径都是 $1 \rightarrow 2 \rightarrow 3$。 对于第二个样例，我们应将城市 $3$ 涂成黑色，并且从 $2$ 到 $4$ 存在黑色和白色两种道路。注意，可能存在一条道路连接某个城市自身。 由 ChatGPT 4.1 翻译