Deskripsi Masalah

Di Amerika Serikat JOI, terdapat $N$ kota yang dinomori dari $1$ hingga $N$, dan $M$ jalan yang dinomori dari $1$ hingga $M$. Jalan $i$ ($1 \le i \le M$) menghubungkan kota $U_i$ dan kota $V_i$ secara dua arah.

Amerika Serikat JOI terdiri dari $K$ negara bagian yang dinomori dari $1$ hingga $K$. Kota $j$ ($1 \le j \le N$) termasuk dalam negara bagian $S_j$. Selain itu, setiap negara bagian memiliki setidaknya $1$ kota.

Direktur K, Menteri Perindustrian Amerika Serikat JOI, berencana untuk melakukan $Q$ perdagangan mulai sekarang. Perdagangan ke-$k$ ($1 \le k \le Q$) adalah mengangkut produk unggulan dari kota $A_k$ ke kota $B_k$ dengan melewati beberapa jalan dan kota. Namun, hanya negara bagian $S_{A_k}$ dan negara bagian $S_{B_k}$ (atau hanya negara bagian $S_{A_k}$ ketika $S_{A_k} = S_{B_k}$) yang bekerja sama dalam perdagangan ini, dan jika rutenya melewati kota mana pun yang bukan milik negara bagian tersebut, produk unggulan akan dicuri.

Direktur K ingin menyelidiki apakah ada rute transportasi untuk melakukan perdagangan tanpa produk unggulannya dicuri. Diberikan susunan kota dan jalan, serta informasi mengenai negara bagian dan perdagangan, buatlah program untuk menentukan bagi setiap perdagangan apakah produk unggulan dapat dikirimkan dengan aman.

Batasan

• $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$).
• Untuk setiap $l$ ($1 \le l \le K$), terdapat $j$ ($1 \le j \le N$) sedemikian sehingga $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$).
• Semua nilai masukan adalah bilangan bulat.

Subsoal

1. ($5$ poin) $N \le 1\,000$, $M \le 1\,000$, $Q \le 1\,000$.
2. ($11$ poin) Semua kota yang termasuk dalam negara bagian $l$ ($1 \le l \le K$) dapat saling bepergian hanya dengan melewati jalan dan kota yang termasuk dalam negara bagian $l$.
3. ($42$ poin) $N \le 80\,000$, $M \le 80\,000$, $Q \le 80\,000$.
4. ($42$ poin) Tidak ada batasan tambahan.

Masukan

Masukan diberikan dari Masukan Standar dalam format berikut:

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

Keluaran

Ke Keluaran Standar, cetak dalam $Q$ baris. Pada baris ke-$k$ ($1 \le k \le Q$), cetak 1 jika produk unggulan dapat dikirimkan pada perdagangan ke-$k$, dan 0 jika tidak mungkin.

Contoh 1

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

1
0
1

• Perdagangan ke-$1$ adalah mengangkut produk unggulan dari kota $1$ ke kota $2$ hanya dengan melewati kota-kota yang termasuk dalam negara bagian $1$ atau negara bagian $2$. Mengangkut melalui kota $1$ → kota $2$ memenuhi syarat, sehingga cetak 1.
• Perdagangan ke-$2$ adalah mengangkut produk unggulan dari kota $1$ ke kota $3$ hanya dengan melewati kota-kota yang termasuk dalam negara bagian $1$. Karena tidak ada rute transportasi yang memenuhi syarat, cetak 0.
• Perdagangan ke-$3$ adalah mengangkut produk unggulan dari kota $1$ ke kota $4$ hanya dengan melewati kota-kota yang termasuk dalam negara bagian $1$ atau negara bagian $2$. Mengangkut melalui kota $1$ → kota $2$ → kota $3$ → kota $4$ memenuhi syarat, sehingga cetak 1.

Masukan contoh ini memenuhi batasan Subsoal $1, 3, 4$.

Contoh 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

Masukan contoh ini memenuhi batasan Subsoal $1, 3, 4$.

Contoh 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

Masukan contoh ini memenuhi batasan semua subsoal.

Contoh 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

Masukan contoh ini memenuhi batasan Subsoal $1, 3, 4$.