009 - ホモドラの襲撃

問題

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

入力

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

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

出力

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

制約

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

• 2≦N≦100000
• 1≦M≦100000
• 1≦Q≦M
• A_i<B_i
• C_i<D_i

---

入出力例

入力例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