/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 個の町と M 個のテレポーターがあり、
町は町 1, 町 2, \ldots, 町N と番号づけられています。
それぞれのテレポーターは 2 つの町を双方向に結んでおり、テレポーターを使用する事によってその 2 つの町の間を 1 分で移動することができます。
i 番目のテレポーターは町 U_i と町 V_i を双方向に結んでいますが、 いくつかのテレポーターについては結ぶ町の片方が決まっておらず、 U_i=0 のときそのテレポーターが結ぶ町の片方は町 V_i であるが、 もう片方が未定であることを意味します。
i=1,2,\ldots,N それぞれについて、次の問題を解いてください。
結ぶ町の片方が未定となっているテレポーターの結ぶ先をすべて町 i とする。 この時に町 1 から町 N まで移動するのに最小で何分かかるか求めよ。 町 1 から町 N までテレポーターのみを使って移動するのが不可能な場合は -1 を出力せよ。
制約
- 2 \leq N \leq 3\times 10^5
- 1\leq M\leq 3\times 10^5
- 0\leq U_i<V_i\leq N
- i \neq j ならば (U_i,V_i)\neq (U_j,V_j)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M U_1 V_1 U_2 V_2 \vdots U_M V_M
出力
N 個の整数を空白区切りで出力せよ。 ここで、k 番目の整数は i=k とした時の問題に対する答えである.
入力例 1
3 2 0 2 1 2
出力例 1
-1 -1 2
結ぶ先が未定となっているテレポーターの結び先を町 1 としたとき、
1 番目と 2 番目のテレポーターはともに町 1 と町 2 を結びます。
このとき、町 1 から町 3 への移動はできません。
結ぶ先が未定となっているテレポーターの結び先を町 2 としたとき、
1 番目のテレポーターは町 2 同士を、 2 番目のテレポーターは町 1 と町 2 を結びます。
このときもやはり、町 1 から町 3 への移動はできません。
結ぶ先が未定となっているテレポーターの結び先を町 3 としたとき、
1 番目のテレポーターは町 3 と町 2 を、 2 番目のテレポーターは町 1 と町 2 を結びます。
この時、次のようにして町 1 から町 3 へ 2 分で移動できます。
- 2 番目のテレポーターを使用し、町 1 から町 2 まで移動する。
- 1 番目のテレポーターを使用し、町 2 から町 3 まで移動する。
よって、-1,-1,2 をこの順に出力します。
結ぶ先が未定となっているテレポーターの結び先によっては、 同じ町同士を結ぶテレポーターが存在する可能性や、 ある 2 つの町を結ぶテレポーターが複数存在する可能性がある事に注意してください。
入力例 2
5 5 1 2 1 3 3 4 4 5 0 2
出力例 2
3 3 3 3 2
Score : 500 points
Problem Statement
There are N towns
numbered Town 1, Town 2, \ldots, Town N.
There are also M Teleporters, each of which connects two towns bidirectionally so that a person can travel from one to the other in one minute.
The i-th Teleporter connects Town U_i and Town V_i bidirectionally. However, for some of the Teleporters, one of the towns it connects is undetermined; U_i=0 means that one of the towns the i-th Teleporter connects is Town V_i, but the other end is undetermined.
For i=1,2,\ldots,N, answer the following question.
When the Teleporters with undetermined ends are all determined to be connected to Town i, how many minutes is required at minimum to travel from Town 1 to Town N? If it is impossible to travel from Towns 1 to N using Teleporters only, print -1 instead.
Constraints
- 2 \leq N \leq 3\times 10^5
- 1\leq M\leq 3\times 10^5
- 0\leq U_i<V_i\leq N
- If i \neq j, then (U_i,V_i)\neq (U_j,V_j).
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M U_1 V_1 U_2 V_2 \vdots U_M V_M
Output
Print N integers, with spaces in between. The k-th integer should be the answer to the question when i=k.
Sample Input 1
3 2 0 2 1 2
Sample Output 1
-1 -1 2
When the Teleporters with an undetermined end are all determined to be connected to Town 1,
the 1-st and the 2-nd Teleporters both connect Towns 1 and 2.
Then, it is impossible to travel from Town 1 to Town 3.
When the Teleporters with an undetermined end are all determined to be connected to Town 2,
the 1-st Teleporter connects Town 2 and itself, and the 2-nd one connects Towns 1 and 2.
Again, it is impossible to travel from Town 1 to Town 3.
When the Teleporters with an undetermined end are all determined to be connected to Town 3,
the 1-st Teleporter connects Town 3 and Town 2, and the 2-nd one connects Towns 1 and 2.
In this case, we can travel from Town 1 to Town 3 in two minutes.
- Use the 2-nd Teleporter to travel from Town 1 to Town 2.
- Use the 1-st Teleporter to travel from Town 2 to Town 3.
Therefore, -1,-1, and 2 should be printed in this order.
Note that, depending on which town the Teleporters with an undetermined end are connected to, there may be a Teleporter that connects a town and itself, or multiple Teleporters that connect the same pair of towns.
Sample Input 2
5 5 1 2 1 3 3 4 4 5 0 2
Sample Output 2
3 3 3 3 2