TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

84.6% (44/52)

Submission's AC Ratio

31.4% (81/258)

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

Sample Output 1

1
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 131072 262144 1
1 5000 131072 262144 1
2 5000 131072 262144 1
3 5000 131072 262144 2
4 5000 131072 262144 2
5 5000 131072 262144 2
6 5000 131072 262144 3
7 5000 131072 262144 3
8 5000 131072 262144 3
9 5000 131072 262144 4
10 5000 131072 262144 4
11 5000 131072 262144 4
12 5000 131072 262144 5
13 5000 131072 262144 5
14 5000 131072 262144 5