No.416 Travel Agency
Problem Statement
Neko-chan runs a travel agency.
The country where Neko-chan lives consists of $N$ islands, island $1$ through island $N$. There are also $M$ bridges, and every bridge connects 2 distinct islands. Bridges can be traversed freely in both directions. The country is not necessarily connected.
Neko-chan's travel agency is located on island $1$. Until now, the agency has kept and managed a list of travel destination candidates, consisting of all towns reachable from island $1$ via bridges.
One day, however, Nezumi-kun invaded the country where Neko-chan lives. Nezumi-kun eats bridges, making them unusable. Since islands that could previously be visited may become unreachable, the managed list is in serious trouble. So Neko-chan has come to you for help.
$Q$ events in which a bridge breaks occur in chronological order. For each island, determine at which destruction it becomes unreachable from island 1.
Input
$N$ $M$ $Q$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_M$ $B_M$ $C_1$ $D_1$ $C_2$ $D_2$ : $C_Q$ $D_Q$
The first line contains the number of islands $N (2 \le N \le 10^5)$, the number of bridges $M(1 \le M \le 2 \times 10^5)$, and the number of bridges that break $Q(1 \le Q \le M)$.
The following $M$ lines, starting from the second line, give information about the existing bridges. The $i$-th of these lines indicates that the $i$-th bridge connects islands $A_i$ and $B_i$. It is guaranteed that $1 \le A_i \lt B_i \le N$, and the same pair ($A_i$, $B_i$) is never given more than once.
The following $Q$ lines give $Q$ pieces of information about the bridges that break. The $j$-th of these lines indicates that the bridge connecting islands $C_j$ and $D_j$ breaks in the $j$-th event. It is guaranteed that $1 \le C_j \lt D_j \le N$, and neither an already broken bridge nor a nonexistent bridge is ever given.
Output
The output consists of $N - 1$ lines.
On the $i$-th line, output the number of the event at which island $i + 1$ became unreachable.
However, if island $i + 1$ is still reachable after all the bridges have been broken, output $-1$.
Also, if island $i + 1$ is unreachable from the beginning, output $0$.
Sample
Sample 1
Input
6 7 5 1 2 1 6 2 4 2 3 3 5 4 5 5 6 2 3 2 4 1 2 4 5 1 6
Output
3 5 4 5 5
Sample 2
Input
10 15 11 1 2 1 3 1 6 2 5 2 9 2 10 3 4 4 6 5 7 5 9 6 7 6 9 8 9 8 10 9 10 1 2 1 3 4 6 5 9 9 10 2 5 6 7 8 9 8 10 3 4 2 9
Output
11 3 3 7 -1 7 9 -1 11
Islands $6$ and $9$ can still be reached even after all the bridges have been broken.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
ei1333333
37zigen