Placeholder

#5858
서브태스크

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

문제

JOI국에는 11에서 NN까지 번호가 매겨진 NN개의 도시와 11에서 MM까지 번호가 매겨진 MM개의 도로가 있습니다. 도로 ii(1≤i≤M1 ≤ i ≤ M)는 도시 UiU_i 와 도시 ViV_i를 양방향으로 연결합니다.

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

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

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


입력

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

NN MM KK

U1U_1 V1V_1

U2U_2 V2V_2

:

UMU_M VMV_M

S1S_1 S2S_2 … SNS_N

QQ

A1A_1 B1B_1

A2A_2 B2B_2

:

AQA_Q BQB_Q


[제한]

2≦N≦400 0002 ≦ N ≦ 400 \,000

1≦M≦400 0001 ≦ M ≦ 400 \,000

1≦K≦N1 ≦ K ≦ N

1≦Ui＜Vi≦N1 ≦ U_i ＜ V_i ≦ N (1≦i≦M1 ≦ i ≦ M)

(Ui,Vi)≠(Uj,Vj)(U_i, V_i) ≠ (U_j, V_j) (1≦i＜j≦M1 ≦ i ＜ j ≦ M)

1≦Sj≦K1 ≦ S_j ≦ K (1≦j≦N1 ≦ j ≦ N)

모든 ll(1≤l≤K1≤l≤K)에 대해 Sj=lS_j = l 이되는 jj(1≤j≤N1≤j≤N) 가 있습니다.

1≦Q≦400 0001 ≦ Q ≦ 400 \,000

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

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

Ak≠BkA_k ≠ B_k (1≦k≦Q1 ≦ k ≦ Q)

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


출력

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


부분문제

번호 점수 조건
#15점

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

#242점

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

#353점

추가 제한 없음.


예제1

입력
4 3 2
1 2
2 3
3 4
1 2 1 2
3
1 2
1 3
1 4
출력
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

입력
4 2 1
1 3
2 4
1 1 1 1
4
1 2
1 3
2 3
2 4
출력
0
1
0
1

예제3

입력
6 5 3
1 2
3 4
5 6
1 4
3 5
1 1 2 2 3 3
4
1 4
1 5
3 6
4 3
출력
1
0
1
1

예제4

입력
8 11 3
4 8
1 8
4 6
3 5
2 4
7 8
6 7
3 4
1 4
2 3
3 8
2 3 1 1 2 1 2 1
10
8 2
8 1
2 7
5 3
5 7
4 8
1 8
6 8
6 5
1 8
출력
1
1
0
1
0
1
1
1
1
1

출처

JOI 2022 예선2


역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.