페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5858
서브태스크

교역 계획 (Trade Plan) 4초 1024MB

문제

JOI국에는 1 에서 N 까지 번호가 매겨진 N 개의 도시와 1 에서 M 까지 번호가 매겨진 M 개의 도로가 있습니다. 도로 i ( 1 ≤ i ≤ M )는 도시 U_i 와 도시 V_i를 양방향으로 연결합니다.

JOI국은 1 에서 K 까지 번호가 매겨진 K 개의 주로 구성됩니다. 도시 j ( 1≤j≤N )는 주 S_j에 속한다. 또한 모든 주에는 적어도 하나 의 도시가 포함됩니다.

JOI국의 산업 장관인 K 이사장은 앞으로 Q 회의 교역을 하고 싶다고 생각하고 있다. k 번째 교역 ( 1≤k≤Q )은 도시 A_k 에서 도시 B_k 로 여러 도로와 도시를 통해 특산품을 운송 합니다 . 다만, 이 교역에 협력해 주는 것은 주 S_{A_k}와 주 S_{A_k}만 (S_{A_k} = S_{B_k}인 경우는 주 S_{A_k}만)이며, 이러한 주에 속하지 않은 도시를 지나가면 특산품은 도난당해 버린다.

K 이사장은 특산품이 도난당하지 않도록 교역을 하는 운송 경로가 있는지 조사하고 싶다. 도시와 도로의 배치, 주와 교역의 정보가 주어졌을 때, 각 교역에 대해 특산품을 무사히 전달할 수 있는지를 판정하는 프로그램을 작성하라.


입력

입력은 다음 형식으로 표준 입력에서 제공됩니다.

N M K

U_1 V_1

U_2 V_2

:

U_M V_M

S_1 S_2 … S_N

Q

A_1 B_1

A_2 B_2

:

A_Q B_Q

[제한]

2 ≦ N ≦ 400 \,000

1 ≦ M ≦ 400 \,000

1 ≦ K ≦ N

1 ≦ U_i ＜ V_i ≦ N (1 ≦ i ≦ M)

(U_i, V_i) ≠ (U_j, V_j) (1 ≦ i ＜ j ≦ M)

1 ≦ S_j ≦ K (1 ≦ j ≦ N)

모든 l ( 1≤l≤K )에 대해 S_j = l 이되는 j ( 1≤j≤N) 가 있습니다.

1 ≦ Q ≦ 400 \,000

1 ≦ Ak ≦ N (1 ≦ k ≦ Q)

1 ≦ Bk ≦ N (1 ≦ k ≦ Q)

A_k ≠ B_k (1 ≦ k ≦ Q)

입력 된 모든 값은 정수입니다．


출력

표준 출력에 Q 행으로 출력하라. k 행째( 1≤k≤Q )에는, k 번째의 교역에 있어서 특산품을 전달하는 것이 가능한 경우를 1 , 불가능한 경우를 0 출력하라.


부분문제

번호 점수 조건
#15점

N ≤ 1\,000 , M ≤ 1\,000 , Q ≤ 1\,000

#242점

N ≤ 80\,000, M ≤ 80\,000, Q ≤ 80\,000

#353점

추가 제한 없음.


예제1

입력
432
12
23
34
1212
3
12
13
14
출력
1
0
1

  • 첫 번째 교역은 주 1 또는 주 2 에 속하는 도시만을 통해 도시 1 에서 도시 2 로 특산품을 수송한다는 것이다. 도시 1 → 도시 2 로 수송하면 조건을 만족하므로 1 출력합니다.

  • 두 번째 교역은 주 1 에 속하는 도시만을 통해 도시 1 에서 도시 3 으로 특산품을 수송한다는 것이다. 조건을 만족하는 운송 경로가 없으므로 0 출력합니다.

  • 세 번째 교역은 주 1 또는 주 2 에 속하는 도시만을 통해 도시 1 에서 도시 4 로 특산품을 수송한다는 것이다. 도시 1 → 도시 2 → 도시 3 → 도시 4 와 수송하면 조건을 만족하므로 1 출력합니다.

이 입력 예제는 작은 문제 1, 3, 4 의 제약 조건을 충족합니다.


예제2

입력
421
13
24
1111
4
12
13
23
24
출력
0
1
0
1

예제3

입력
653
12
34
56
14
35
112233
4
14
15
36
43
출력
1
0
1
1

예제4

입력
8113
48
18
46
35
24
78
67
34
14
23
38
23112121
10
82
81
27
53
57
48
18
68
65
18
출력
1
1
0
1
0
1
1
1
1
1

출처

JOI 2022 예선2

역링크