Treść zadania

W Stanach Zjednoczonych JOI znajduje się $N$ miast ponumerowanych od $1$ do $N$ oraz $M$ dróg ponumerowanych od $1$ do $M$. Droga $i$ ($1 \le i \le M$) łączy dwukierunkowo miasto $U_i$ z miastem $V_i$.

Stany Zjednoczone JOI dzielą się na $K$ stanów ponumerowanych od $1$ do $K$. Miasto $j$ ($1 \le j \le N$) należy do stanu $S_j$. Ponadto w każdym stanie znajduje się co najmniej $1$ miasto.

Dyrektor K, minister przemysłu Stanów Zjednoczonych JOI, planuje przeprowadzić $Q$ transakcji handlowych. $k$-ta transakcja ($1 \le k \le Q$) polega na przetransportowaniu regionalnych specjałów z miasta $A_k$ do miasta $B_k$ przez pewne drogi i miasta. Jednak w tej transakcji współpracują wyłącznie stan $S_{A_k}$ oraz stan $S_{B_k}$ (lub tylko stan $S_{A_k}$, gdy $S_{A_k} = S_{B_k}$), a jeśli trasa przebiega przez jakiekolwiek miasto nienależące do tych stanów, specjały zostaną skradzione.

Dyrektor K chce zbadać, czy istnieje trasa transportowa pozwalająca na przeprowadzenie transakcji bez kradzieży specjałów. Mając dany układ miast i dróg oraz informacje o stanach i transakcjach, napisz program, który dla każdej transakcji rozstrzygnie, czy można bezpiecznie dostarczyć specjały.

Ograniczenia

• $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$).
• Dla każdego $l$ ($1 \le l \le K$) istnieje takie $j$ ($1 \le j \le N$), że $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$).
• Wszystkie wartości wejściowe są liczbami całkowitymi.

Podzadania

1. ($5$ punktów) $N \le 1\,000$, $M \le 1\,000$, $Q \le 1\,000$.
2. ($11$ punktów) Wszystkie miasta należące do stanu $l$ ($1 \le l \le K$) mogą komunikować się ze sobą, korzystając wyłącznie z dróg oraz miast należących do stanu $l$.
3. ($42$ punktów) $N \le 80\,000$, $M \le 80\,000$, $Q \le 80\,000$.
4. ($42$ punktów) Brak dodatkowych ograniczeń.

Wejście

Wejście jest podawane ze standardowego wejścia w następującym formacie:

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

Wyjście

Na standardowe wyjście wypisz $Q$ wierszy. W $k$-tym wierszu ($1 \le k \le Q$) wypisz 1, jeśli w $k$-tej transakcji można dostarczyć specjały, lub 0, jeśli jest to niemożliwe.

Przykład 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$-sza transakcja polega na przetransportowaniu specjałów z miasta $1$ do miasta $2$, przechodząc wyłącznie przez miasta należące do stanu $1$ lub stanu $2$. Transport trasą miasto $1$ → miasto $2$ spełnia warunek, więc wypisujemy 1.
• $2$-ga transakcja polega na przetransportowaniu specjałów z miasta $1$ do miasta $3$, przechodząc wyłącznie przez miasta należące do stanu $1$. Ponieważ nie istnieje trasa transportowa spełniająca warunek, wypisujemy 0.
• $3$-cia transakcja polega na przetransportowaniu specjałów z miasta $1$ do miasta $4$, przechodząc wyłącznie przez miasta należące do stanu $1$ lub stanu $2$. Transport trasą miasto $1$ → miasto $2$ → miasto $3$ → miasto $4$ spełnia warunek, więc wypisujemy 1.

Ten przykład wejściowy spełnia ograniczenia podzadań $1, 3, 4$.

Przykład 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

Ten przykład wejściowy spełnia ograniczenia podzadań $1, 3, 4$.

Przykład 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

Ten przykład wejściowy spełnia ograniczenia wszystkich podzadań.

Przykład 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

Ten przykład wejściowy spełnia ograniczenia podzadań $1, 3, 4$.