問題一覧 > 通常問題

No.416 Travel Agency

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 193
作問者 : ei1333333 / テスター : 37zigen
お気に入りにしたユーザー ProblemId : 1229 / 自分の提出
問題文最終更新日: 2026-06-25 15:04:58
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 147 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。