Умова задачі

У Сполучених Штатах JOI є $N$ міст, пронумерованих від $1$ до $N$, та $M$ доріг, пронумерованих від $1$ до $M$. Дорога $i$ ($1 \le i \le M$) з'єднує місто $U_i$ та місто $V_i$ в обох напрямках.

Сполучені Штати JOI складаються з $K$ штатів, пронумерованих від $1$ до $K$. Місто $j$ ($1 \le j \le N$) належить штату $S_j$. Крім того, у кожному штаті є принаймні $1$ місто.

Директор K, міністр промисловості Сполучених Штатів JOI, планує провести $Q$ торговельних операцій. $k$-та торговельна операція ($1 \le k \le Q$) полягає у перевезенні фірмових товарів із міста $A_k$ до міста $B_k$ через деякі дороги та міста. Проте в цій операції співпрацюють лише штат $S_{A_k}$ і штат $S_{B_k}$ (або лише штат $S_{A_k}$, якщо $S_{A_k} = S_{B_k}$), і якщо маршрут проходить через будь-яке місто, що не належить цим штатам, фірмові товари буде вкрадено.

Директор K хоче з'ясувати, чи існує маршрут перевезення, який дозволяє провести торгівлю без крадіжки фірмових товарів. За заданим розташуванням міст і доріг, а також інформацією про штати та торговельні операції, напишіть програму, яка для кожної операції визначить, чи можна безпечно доставити фірмові товари.

Обмеження

• $2 \le N \le 400\,000$.
• $1 \le M \le 400\,000$.
• $1 \le K \le N$.
• $1 \le U_i < V_i \le N$ ($1 \le i \le M$).
• $(U_i, V_i) \neq (U_j, V_j)$ ($1 \le i < j \le M$).
• $1 \le S_j \le K$ ($1 \le j \le N$).
• Для кожного $l$ ($1 \le l \le K$) існує $j$ ($1 \le j \le N$), такий що $S_j = l$.
• $1 \le Q \le 400\,000$.
• $1 \le A_k \le N$ ($1 \le k \le Q$).
• $1 \le B_k \le N$ ($1 \le k \le Q$).
• $A_k \neq B_k$ ($1 \le k \le Q$).
• Усі вхідні значення є цілими числами.

Підзадачі

1. ($5$ балів) $N \le 1\,000$, $M \le 1\,000$, $Q \le 1\,000$.
2. ($11$ балів) Між будь-якими містами, що належать штату $l$ ($1 \le l \le K$), можна переміщуватися, проходячи лише дорогами та містами, що належать штату $l$.
3. ($42$ бали) $N \le 80\,000$, $M \le 80\,000$, $Q \le 80\,000$.
4. ($42$ бали) Додаткових обмежень немає.

Вхідні дані

Вхідні дані подаються зі стандартного потоку вводу в такому форматі:

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

Вихідні дані

У стандартний потік виводу виведіть $Q$ рядків. У $k$-му рядку ($1 \le k \le Q$) виведіть 1, якщо в $k$-й торговельній операції можливо доставити фірмові товари, і 0, якщо це неможливо.

Приклад 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$-ша торговельна операція полягає у перевезенні фірмових товарів із міста $1$ до міста $2$ лише через міста, що належать штату $1$ або штату $2$. Перевезення за маршрутом місто $1$ → місто $2$ задовольняє умову, тому виводиться 1.
• $2$-га торговельна операція полягає у перевезенні фірмових товарів із міста $1$ до міста $3$ лише через міста, що належать штату $1$. Оскільки маршруту перевезення, що задовольняє умову, не існує, виводиться 0.
• $3$-тя торговельна операція полягає у перевезенні фірмових товарів із міста $1$ до міста $4$ лише через міста, що належать штату $1$ або штату $2$. Перевезення за маршрутом місто $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

Цей приклад вхідних даних задовольняє обмеження підзадач $1, 3, 4$.

Приклад 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

Цей приклад вхідних даних задовольняє обмеження підзадач $1, 3, 4$.