Egor in the Republic of Dagestan
Contest: Codeforces Round 669 (Div. 2)
Difficulty rating: 2500
Tags: constructive algorithms, dfs and similar, dp, graphs, greedy, shortest paths

Egor is a famous Russian singer, rapper, actor and blogger, and finally he decided to give a concert in the sunny Republic of Dagestan.

There are $$$n$$$ cities in the republic, some of them are connected by $$$m$$$ directed roads without any additional conditions. In other words, road system of Dagestan represents an arbitrary directed graph. Egor will arrive to the city $$$1$$$, travel to the city $$$n$$$ by roads along some path, give a concert and fly away.

As any famous artist, Egor has lots of haters and too annoying fans, so he can travel only by safe roads. There are two types of the roads in Dagestan, black and white: black roads are safe at night only, and white roads — in the morning. Before the trip Egor's manager's going to make a schedule: for each city he'll specify it's color, black or white, and then if during the trip they visit some city, the only time they can leave it is determined by the city's color: night, if it's black, and morning, if it's white. After creating the schedule Egor chooses an available path from $$$1$$$ to $$$n$$$, and for security reasons it has to be the shortest possible.

Egor's manager likes Dagestan very much and wants to stay here as long as possible, so he asks you to make such schedule that there would be no path from $$$1$$$ to $$$n$$$ or the shortest path's length would be greatest possible.

A path is one city or a sequence of roads such that for every road (excluding the first one) the city this road goes from is equal to the city previous road goes into. Egor can move only along paths consisting of safe roads only.

The path length is equal to the number of roads in it. The shortest path in a graph is a path with smallest length.

Input format:
The first line contains two integers $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 500000$$$, $$$0 \leq m \leq 500000$$$) — the number of cities and the number of roads.

The $$$i$$$-th of next $$$m$$$ lines contains three integers — $$$u_i$$$, $$$v_i$$$ and $$$t_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$t_i \in \{0, 1\}$$$) — numbers of cities connected by road and its type, respectively ($$$0$$$ — night road, $$$1$$$ — morning road).

Output format:
In the first line output the length of the desired path (or $$$-1$$$, if it's possible to choose such schedule that there's no path from $$$1$$$ to $$$n$$$).

In the second line output the desired schedule — a string of $$$n$$$ digits, where $$$i$$$-th digit is $$$0$$$, if the $$$i$$$-th city is a night one, and $$$1$$$ if it's a morning one.

If there are multiple answers, print any.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first sample, if we paint city $$$1$$$ white, the shortest path is $$$1 \rightarrow 3$$$. Otherwise, it's $$$1 \rightarrow 2 \rightarrow 3$$$ regardless of other cities' colors.

For the second sample, we should paint city $$$3$$$ black, and there are both black and white roads going from $$$2$$$ to $$$4$$$. Note that there can be a road connecting a city with itself.

Example input:
3 4
1 2 0
1 3 1
2 3 0
2 3 1

Example output:
2
011

Example input:
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

Example output:
3
1101

Editorial:
**This task has a simple intuitive proof, but I wanted to describe it formally so it's pretty complicated.**
We'll show a constructive algorithm for this task and proof it's correctness. We also provide a realisation with $$$O(n+m)$$$ time complexity.
Let's change each edge's direction to the opposite. Then for vertex of color $$$c$$$ all incoming edges of color $$$c$$$ and only they are safe. We call a schedule optimal for $$$x$$$ if the shortest path (from $$$n$$$) to $$$x$$$ along the safe edges is the longest possible. We call a path (from $$$n$$$) to $$$x$$$ optimal if it's the shortest path for any optimal schedule for $$$x$$$. So we have to find an optimal schedule for $$$1$$$ and the length of optimal path for $$$1$$$.
Let's make four parameters for each vertex $$$x$$$:
$$$b[x]$$$ - the length of optimal path to $$$x$$$, if $$$x$$$ is black,
$$$w[x]$$$ - the length of optimal path to $$$x$$$, if $$$x$$$ is white,
$$$dp[x]$$$ - the length of optimal path to $$$x$$$ among all possible schedules,
$$$col[x]$$$ - the color of $$$x$$$.
The algorithm is following:
1. Initially $$$b[n]=w[n]=dp[n]=0$$$, $$$b[x]=w[x]=dp[x]=+\infty$$$ for all $$$x\neq n$$$. All vertices are unpainted.
2. If there is no unpainted vertex $$$x$$$ such that $$$dp[x]<+\infty$$$ (including the case when all vertices are painted) - go to point $$$6$$$
3. Among all unpainted vertices choose vertex $$$u$$$ with the smallest possible value of $$$dp[u]$$$. If $$$b[u] > w[u]$$$ set $$$col[u]=0$$$.If $$$w[u] > b[u]$$$ set $$$col[u]=1$$$.If $$$w[u] = b[u]$$$ then $$$col[u]$$$ can be either $$$0$$$ or $$$1$$$.
4. Watch each edge $$$(u, v)$$$ outgoing from $$$u$$$. Let an edge's color be $$$t$$$.If $$$t=0$$$ (black edge) - set $$$b[v]=min(b[v], dp[u]+1)$$$.If $$$t=1$$$ (white edge) - set $$$w[v]=min(w[v], dp[u]+1)$$$.Then set $$$dp[v]=max(b[v], w[v])$$$.
5. Go to point $$$2$$$.
6. For each unpainted vertex set the color just as in point $$$3$$$.
7. The value of $$$dp[1]$$$ is equal to the desired answer (excluding $$$dp[1]=\infty$$$ case: that means there's no way from $$$n$$$ to $$$1$$$ for the constructed schedule, and the answer is $$$-1$$$), and the values of $$$col$$$ form the optimal schedule.
Correctness proof
Let $$$lb[x]$$$, $$$lw[x]$$$ and $$$l[x]$$$ be the real optimal values of $$$b[x]$$$, $$$w[x]$$$ and $$$dp[x]$$$. We'll show that the parameters found by the algorithm are optimal. Let's proof some statements:
1. Any optimal path is simple. This statement is obvious, because the shortest path in any graph doesn't contain repeating vertices.
2. For any black edge $$$(u, v$$$) $$$l[u]+1\geq lb[v]$$$. For any schedule the length of the shortest path from $$$n$$$ to $$$u$$$ is not greater than $$$l[u]$$$, and the color of $$$v$$$ is fixed, so the length of the shortest path from $$$n$$$ to $$$v$$$ is not greater than $$$l[u]+1$$$. For white edges and correspondingly $$$lw[u]$$$ the analogous statement is correct.
3. $$$b[x]\geq lb[x]$$$, $$$w[x]\geq lw[x]$$$ for any vertex $$$x$$$ at every moment. Before the first iteration the statement $$$3$$$ is correct. Let $$$u$$$ be selected in the beginning of some iteration, and we update the parameters of $$$v$$$ for a black edge $$$(u, v)$$$. Let the statement $$$3$$$ be correct before the update. Then due to the statement $$$2$$$ $$$l[u]+1\geq lb[v]$$$. $$$b[u]\geq lb[u]$$$ and $$$w[u]\geq lw[u]$$$, so $$$dp[u]=max(b[u],w[u])\geq l[u]=max(lb[u],lw[u])$$$, and $$$dp[u]+1\geq l[u]+1\geq lb[v]$$$. After the update the value of $$$b[v]$$$ can stay the same or be changed to $$$dp[u]+1$$$, but since as $$$b[v]\geq l[v]$$$, the final value of $$$b[v]$$$ is not less than $$$l[v]$$$, so the statement $$$3$$$ remains correct after the update. Analogously we can show that for white edges it's correct, too. By induction we have that the statement $$$3$$$ is invariant, i.e. it's always correct.
We can notice that for each painted vertex $$$x$$$ it's value of $$$dp[x]$$$ is not smaller than the value of $$$dp[y]$$$ for any vertex $$$y$$$ painted before the $$$x$$$. Also, the values of $$$dp[x]$$$, $$$b[x]$$$ and $$$w[x]$$$ remain constant after the iteration when $$$x$$$ is painted. These facts are easy-to-proof, but for shortness we won't do it here.
Lemma:  in the end of the $$$k$$$-th iteration for each vertex $$$x$$$ the values of $$$b[x]$$$, $$$w[x]$$$ and $$$dp[x]$$$ correspond to the shortest (for the current schedule) paths passing through the painted vertices only (excluding $$$x$$$).
Proof: we'll show it by induction on the number of iterations.
It's easy to see that after the first iteration the Lemma remains correct.
Let the Lemma be correct after the first $$$k$$$ iterations. Let $$$x$$$ be painted during the $$$(k+1)$$$-th iteration. Then $$$b[x]$$$ and $$$w[x]$$$ are already equal to the lengths of shortest paths to $$$x$$$, passing through painted vertices only and ending by black and white edges, correspondingly (it's obvious, proof it yourself if you don't believe). The length of the shortest path for already painted vertices won't change, because $$$dp[x]$$$ is not smaller than the values of $$$dp$$$ of previously painted vertices.
Thus, at the end of the algorithm we get the desired schedule, where $$$dp[x]$$$ for each $$$x$$$ is equal to the length of the shortest path to $$$x$$$, and $$$dp[x]\geq l[x]$$$; then from these two statements follows the fact that $$$dp[x]=l[x]$$$ for all vertices $$$x$$$, what means that the constructed schedule is optimal.
Realisation
This algorithm can be realised as a modified BFS, where the vertex is added to the queue just as it's value becomes smaller than infinity (in the code the value of «infinity» can be just $$$n$$$). It's easy to proof that such realisation is equivalent to the algorithm.