Problem Description

In the JOI United States, there are $ N $ cities numbered from $ 1 $ to $ N $ and $ M $ roads numbered from $ 1 $ to $ M $. Road $ i $ ($1 \leq i \leq M$) connects city $ U_i $ and city $ V_i $ bidirectionally.

The JOI United States consists of $ K $ states numbered from $ 1 $ to $ K $. City $ j $ ($1 \leq j \leq N$) belongs to state $ S_j $. Also, each state contains at least one city.

K, the Minister of Industry in the JOI United States, plans to conduct $ Q $ trades. The $ k $-th trade ($1 \leq k \leq Q$) involves transporting specialty products from city $ A_k $ to city $ B_k $ through some roads and cities. However, only the states $ S_{A_k} $ and $ S_{B_k} $ (or only state $ S_{A_k} $ if $ S_{A_k} = S_{B_k} $) will cooperate in this trade, and passing through cities not belonging to these states will result in the theft of the specialty products.

K wants to investigate whether there is a route for the trade that prevents the specialty products from being stolen. Given the arrangement of cities and roads, the information about states and trades, create a program to determine for each trade whether it is possible to deliver the specialty products safely.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ K $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $\vdots$ $ U_M $ $ V_M $ $ S_1 $ $ S_2 $ $\cdots$ $ S_N $ $ Q $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $\vdots$ $ A_Q $ $ B_Q $

Output Format

Output $ Q $ lines to the standard output. The $ k $-th line ($1 \leq k \leq Q$) should contain 1 if it is possible to deliver the specialty products in the $ k $-th trade, and 0 otherwise.

Sample Input and Output

Sample Input #1

4 3 2
1 2
2 3
3 4
1 2 1 2
3
1 2
1 3
1 4

Sample Output #1

1
0
1

Sample Input #2

4 2 1
1 3
2 4
1 1 1 1
4
1 2
1 3
2 3
2 4

Sample Output #2

0
1
0
1

Sample Input #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

Sample Output #3

1
0
1
1

Sample Input #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

Sample Output #4

1
1
0
1
0
1
1
1
1
1

Notes/Hints

Constraints

• $2 \leq N \leq 400,000$.
• $1 \leq M \leq 400,000$.
• $1 \leq K \leq N$.
• $1 \leq U_i < V_i \leq N$ ($1 \leq i \leq M$).
• $(U_i, V_i) \neq (U_j, V_j)$ ($1 \leq i < j \leq M$).
• $1 \leq S_j \leq K$ ($1 \leq j \leq N$).
• For all $ l $ ($1 \leq l \leq K$), there exists $ j $ ($1 \leq j \leq N$) such that $ S_j = l $.
• $1 \leq Q \leq 400,000$.
• $1 \leq A_k \leq N$ ($1 \leq k \leq Q$).
• $1 \leq B_k \leq N$ ($1 \leq k \leq Q$).
• $A_k \neq B_k$ ($1 \leq k \leq Q$).
• All input values are integers.

Subtasks

1. ($ 5 $ points) $N \leq 1,000$, $M \leq 1,000$, $Q \leq 1,000$.
2. ($ 11 $ points) All cities belonging to state $ l $ ($1 \leq l \leq K$) can travel to each other through roads and cities belonging to state $ l $.
3. ($ 42 $ points) $N \leq 80,000$, $M \leq 80,000$, $Q \leq 80,000$.
4. ($ 42 $ points) No additional constraints.

Grading Notes

All submissions are graded on the judge system.

A submitted source code is considered correct for a subtask if it returns the correct result for all test inputs corresponding to that subtask.

The score for each submission is the sum of the points for the subtasks that the submitted source code is considered correct for.

The score for this task is the maximum score of all submissions for this task.

The current score can be checked under the "My Score" tab in the "Submission Results".

见题面 Input 部分

见题面 Output 部分