Oppgavebeskrivelse

I JOIs forente stater er det $N$ byer nummerert fra $1$ til $N$, og $M$ veier nummerert fra $1$ til $M$. Vei $i$ ($1 \le i \le M$) forbinder by $U_i$ og by $V_i$ i begge retninger.

JOIs forente stater består av $K$ delstater nummerert fra $1$ til $K$. By $j$ ($1 \le j \le N$) tilhører delstat $S_j$. I tillegg inneholder hver delstat minst $1$ by.

Direktør K, industriministeren i JOIs forente stater, planlegger å gjennomføre $Q$ handler fremover. Den $k$-te handelen ($1 \le k \le Q$) går ut på å transportere spesialprodukter fra by $A_k$ til by $B_k$ via noen veier og byer. Imidlertid samarbeider kun delstat $S_{A_k}$ og delstat $S_{B_k}$ (eller kun delstat $S_{A_k}$ når $S_{A_k} = S_{B_k}$) i denne handelen, og hvis ruten passerer gjennom en by som ikke tilhører disse delstatene, vil spesialproduktene bli stjålet.

Direktør K ønsker å undersøke om det finnes en transportrute for å gjennomføre handelen uten at spesialproduktene blir stjålet. Gitt plasseringen av byer og veier, samt informasjon om delstatene og handlene, skriv et program som for hver handel avgjør om det er mulig å levere spesialproduktene trygt.

Begrensninger

• $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$).
• For hver $l$ ($1 \le l \le K$) finnes det en $j$ ($1 \le j \le N$) slik at $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$).
• Alle inndataverdier er heltall.

Deloppgaver

1. ($5$ poeng) $N \le 1\,000$, $M \le 1\,000$, $Q \le 1\,000$.
2. ($11$ poeng) Alle byer som tilhører delstat $l$ ($1 \le l \le K$) kan reise mellom hverandre ved kun å passere gjennom veier og byer som tilhører delstat $l$.
3. ($42$ poeng) $N \le 80\,000$, $M \le 80\,000$, $Q \le 80\,000$.
4. ($42$ poeng) Ingen ytterligere begrensninger.

Inndata

Inndata gis fra standard inndata på følgende format:

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

Utdata

Skriv ut $Q$ linjer til standard utdata. På den $k$-te linjen ($1 \le k \le Q$) skal du skrive ut 1 hvis det er mulig å levere spesialproduktene i den $k$-te handelen, og 0 hvis det er umulig.

Eksempel 1

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

1
0
1

• Den $1$. handelen går ut på å transportere spesialprodukter fra by $1$ til by $2$ ved kun å passere gjennom byer som tilhører delstat $1$ eller delstat $2$. Transport langs by $1$ → by $2$ oppfyller betingelsen, så vi skriver ut 1.
• Den $2$. handelen går ut på å transportere spesialprodukter fra by $1$ til by $3$ ved kun å passere gjennom byer som tilhører delstat $1$. Siden det ikke finnes noen transportrute som oppfyller betingelsen, skriver vi ut 0.
• Den $3$. handelen går ut på å transportere spesialprodukter fra by $1$ til by $4$ ved kun å passere gjennom byer som tilhører delstat $1$ eller delstat $2$. Transport langs by $1$ → by $2$ → by $3$ → by $4$ oppfyller betingelsen, så vi skriver ut 1.

Dette eksempelet oppfyller begrensningene i deloppgave $1, 3, 4$.

Eksempel 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

Dette eksempelet oppfyller begrensningene i deloppgave $1, 3, 4$.

Eksempel 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

Dette eksempelet oppfyller begrensningene i alle deloppgaver.

Eksempel 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

Dette eksempelet oppfyller begrensningene i deloppgave $1, 3, 4$.