1798 . Can You Arrive?
TopCoder
Tags
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 1
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
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
1
0
0
1
1
0
0
Hints
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~2 | 20 |
| 2 | 3~5 | 20 |
| 3 | 6~8 | 20 |
| 4 | 9~11 | 20 |
| 5 | 12~14 | 20 |