問題文

ねこちゃんは旅行会社を経営しています。

ねこちゃんが住む国は, 島 $1$ から 島 $N$ までの $N$ 個の島からなります。また, $M$ 本の橋があり, すべての橋は異なる 2 つの島を結んでいます。 橋は双方向に自由に移動可能です。必ずしも連結とは限りません。

ねこちゃんの旅行会社は, 島 $1$ に存在します。 今まで, 島 $1$ から橋を通って到達可能なすべての街を旅行先の候補として, それをリスト化し管理してきました。

しかしある日, ねこちゃんが住む国にねずみくんが侵略してきました。ねずみくんは橋を食べて, その橋を使えなくしてしまいます。 今まで旅行できた島にいけなくなることが起こるので, 管理してきたリストが大変なことになってしまいます。 そこであなたに助けを求めてきました。

橋が壊れるイベントが時系列順に $Q$ 回発生します。それぞれの島について, 何回目の破壊で島 1 から到達できなくなるかを調べてください。

入力

$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$

1 行目に, 島の数 $N(2\le N\le {10}^5)$, 橋の数 $M(1\le M\le 2\times {10}^5)$, 壊れる橋の数 $Q(1\le Q\le M)$ が与えられます。

2 行目から $M$ 行にかけて存在する橋の情報が与えられます。 このうち $i$ 行目は $i$ 番目の橋が島 $A_i$ と $B_i$ を結んでいることを表します。 $1\le A_i<B_i\le N$ が保証され, 同じ ($A_i$, $B_i$) の組が与えられることはありません。

その後 $Q$ 行にかけて壊れる橋の情報が $Q$ 個与えられます。 このうち $j$ 行目は, $j$ 回目のイベントで島 $C_j$ と $D_j$ を結ぶ橋が壊れることを表します。 $1\le C_j<D_j\le N$ が保証され, 一度壊れた橋や存在しない橋が与えられることはありません。

出力

出力は $N-1$ 行からなります。

$i$ 行目には, 何回目のイベントで島 $i+1$ に到達できなくなったかを出力してください。

ただし, 橋がすべて壊された後も島 $i+1$ に到達できるとき, $-1$ を出力してください。

また, 島 $i+1$ に最初から到達できないとき, $0$ を出力してください。

サンプル

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

3
5
4
5
5

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

11
3
3
7
-1
7
9
-1
11