叶戈尔是俄罗斯著名歌手、说唱歌手、演员和博主,最后他决定在阳光明媚的达吉斯坦共和国举办音乐会。
共和国有 $$$n$$$ 个城市,其中一些由 $$$m$$$ 有向道路连接,没有任何附加条件。换句话说,达吉斯坦的道路系统代表任意有向图。叶戈尔将抵达城市$$$1$$$,沿着某条道路前往城市$$$n$$$,举办一场音乐会,然后飞走。
与任何著名艺术家一样,叶戈尔有很多仇恨者和讨厌的粉丝,所以他只能走安全的道路。达吉斯坦有两种类型的道路,黑色和白色:黑色道路仅在夜间安全,白色道路在早晨安全。在旅行之前,叶戈尔的经理会制定一个时间表:对于每个城市,他都会指定它的颜色,黑色或白色,然后如果在旅行期间他们访问某个城市,他们唯一可以离开的时间由该城市的颜色决定:如果是黑色,则为晚上,如果为白色,则为早晨。创建计划后,Egor 选择一条从 $$$1$$$ 到 $$$n$$$ 的可用路径,出于安全原因,它必须尽可能短。
叶戈尔的经理非常喜欢达吉斯坦,希望在这里呆得尽可能久,所以他要求你制定这样的时间表,从$$$1$$$到$$$n$$$没有路径,或者最短路径的长度尽可能最大。
路径是一个城市或一系列道路,对于每条道路(不包括第一条),这条道路出发的城市等于前一条道路进入的城市。叶戈尔只能沿着仅由安全道路组成的路径移动。
路径长度等于其中的道路数量。图中的最短路径是长度最小的路径。
输入
第一行包含两个整数 $$$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$$$,如果可以选择这样的时间表,即没有从 $$$1$$$ 到 $$$n$$$ 的路径)。
在第二行中输出所需的时间表 - 一串 $$$n$$$ 数字,其中 $$$i$$$ 位数字是 $$$0$$$,如果第 $$$i$$$ 位城市是夜间城市,如果是早晨城市,则为 $$$1$$$。
如果有多个答案,请打印其中一个。
示例
输入 #1
3 4 1 2 0 1 3 1 2 3 0 2 3 1
输出 #1
2 011
输入 #2
4 8 1 1 0 1 3 0 1 3 1 3 2 0 2 1 0 3 4 1 2 4 0 2 4 1
输出 #2
3 1101
输入 #3
5 10 1 2 0 1 3 1 1 4 0 2 3 0 2 3 1 2 5 0 3 4 0 3 4 1 4 2 1 4 5 0
输出 #3
-1 11111
注意
对于第一个示例,如果我们将城市 $$$1$$$ 涂成白色,则最短路径为 $$$1 \rightarrow 3$$$。否则,无论其他城市的颜色如何,它都是 $$$1 \rightarrow 2 \rightarrow 3$$$。
对于第二个示例,我们应该将城市 $$$3$$$ 涂成黑色,并且从 $$$2$$$ 到 $$$4$$$ 有黑色和白色的道路。请注意,可以有一条道路将城市与其本身连接起来。