009 - ホモドラの襲撃

時間制限 1 秒 / メモリ制限 64 MB / 得点 15 / x 1 /


TLE
1sec
MLE
64MB
得点
15

問題

ブルーインザス海には、N個の島が浮かんでいる。これらの島には1番からN番の番号が振られている。
そして、それらの島は合計M本の橋で結ばれている。
これまで平和な生活を営んできたイチモウダ人だったが、ある日、ホモノドラゴン、略してホモドラがブルーインザス海にやってきた。
ホモドラは男に目がない。逃げまとうイチモウダ人を捕まえようとするあまり、島と島の間にまたがる橋を壊してしまった。
イチモウダ人のミツイは、島1に家を持ち、仕事の都合上家からそれぞれの島に移動する必要がある。
しかし、今回橋を壊されたことにより、島1からはいけなくなる島が出てくる可能性が出てきた。
今回橋が壊された回数はQ回である。
島1からいけなくなる島がある場合、何回目の破壊でいけなくなるかを調べてほしい。

入力

N M Q
A1 B1
A2 B2
.
.
.
AM BM
C1 D1
C2 D2
.
.
.
CQ DQ

1行目には、島の数Nと、橋の数Mと、破壊した橋の数Qが整数かつ空白区切りで与えられる。
2行目からM行にわたって、橋の情報が与えられる。AiBiの間に橋があることを示し、同じ(Ai,Bi)の組が2回以上書かれることはない。
続くQ行には、破壊された橋の情報が与えられる。i番目に、CiDiの間の橋が破壊されたことを表す。一度破壊された橋や、存在しない橋が破壊されることはない。

出力

各島について、1番から順にN番まで調査した結果を出力する。1つの島について出力するごとに改行する。
もしi番めの島が、橋が全て壊された後も島1から移動できる場合は-1を出力する。
もしi番めの島が、最初に橋が壊されるよりも前に島1から移動できない場合は0を出力する。
それ以外の場合(橋が壊されることによって移動できなくなる場合)は、何回目の破壊でいけなくなったかを出力する。

制約

全ての入出力ケースについて以下を満たす。

  • 2≦N≦100000
  • 1≦M≦100000
  • 1≦Q≦M
  • Ai<Bi
  • Ci<Di

入出力例

入力例1

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

出力例1

-1
3
5
4
5
5

入力例2

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

出力例2

-1
11
3
3
7
-1
7
9
-1
11