TopCoder

Thumb rezero
Re Zero
Re Zero

User's AC Ratio

95.0% (19/20)

Submission's AC Ratio

41.1% (23/56)

Description

注意:
本題測資改為1base。

你,もも,是個四處旅行的旅行家,理所當然的對各地的地鐵系統非常熟悉。
今天你一如往常的走在路上,
突然,有一團又一團的妹子來向你問路,
熱心的你當然無法拒絕別人的要求。

你知道在每個不同的地方有不同的地鐵系統,
謹慎的你早就把各地的地鐵都畫好了,
你希望快點回答完妹子們的問題,
這樣你就可以早點跟她們,嘿嘿,你這樣暗算著。

你知道地鐵的資訊大概是這樣:
$N$個站,$M$條軌道,$K$段行駛路線,
站與站之間使用軌道連接,
保證軌道不會形成環,且$M$ = $N-1$,
每段行駛路線代表有一輛車在兩站來回發車。

你知道妹子的資訊大概是這樣:
$Q$位妹子來向你問路,問你能不能從某一站經過任意多次的轉車搭到另一站。
保證兩站不是同一站。

Input Format

第一行輸入四個正整數$N, M, K, Q$意義如題目敘述
接著有$M$行數對 $m_{i}, m_{j}$代表這兩站間有一條軌道連接
接著有$K$行數對 $k_{i}, k_{j}$代表有一輛車行駛於這兩站間
接著有$Q$行數對 $q_{i}, q_{j}$問你這兩站間能不能經過有限次的轉乘到達

第一子題滿足:$N \leq 10 $, $Q \leq 10$
第二子題滿足:$N \leq 100 $, $Q \leq 100$
第三子題滿足:$N \leq 10000 $

對於所有子題滿足:$N \leq 1000000$,$M = N-1$,$K \leq N$,$Q \leq 1000000 $

Output Format

對於每一筆詢問
如果可以到達請輸出1
否則輸出0

Sample Input

11 10 3 5
1 2
2 3
2 6
3 4
3 5
1 7
7 8
8 9
9 10
9 11
4 5
6 8
7 10
1 2
3 4
1 10
4 10
10 11

Sample Output

1
1
1
0
0

Hints

Problem Source

Subtasks

For Testdata: 0 ~ 2, Score: 20
For Testdata: 3 ~ 5, Score: 20
For Testdata: 6 ~ 8, Score: 20
For Testdata: 9 ~ 11, Score: 20
For Testdata: 12 ~ 14, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 131072 262144
1 5000 131072 262144
2 5000 131072 262144
3 5000 131072 262144
4 5000 131072 262144
5 5000 131072 262144
6 5000 131072 262144
7 5000 131072 262144
8 5000 131072 262144
9 5000 131072 262144
10 5000 131072 262144
11 5000 131072 262144
12 5000 131072 262144
13 5000 131072 262144
14 5000 131072 262144