Tehtävänanto

JOI:n yhdysvalloissa on $N$ kaupunkia, jotka on numeroitu $1$:stä $N$:ään, ja $M$ tietä, jotka on numeroitu $1$:stä $M$:ään. Tie $i$ ($1 \le i \le M$) yhdistää kaupungin $U_i$ ja kaupungin $V_i$ kaksisuuntaisesti.

JOI:n yhdysvallat koostuu $K$ osavaltiosta, jotka on numeroitu $1$:stä $K$:hon. Kaupunki $j$ ($1 \le j \le N$) kuuluu osavaltioon $S_j$. Lisäksi jokaisessa osavaltiossa on vähintään $1$ kaupunki.

Johtaja K, JOI:n yhdysvaltojen teollisuusministeri, suunnittelee tekevänsä $Q$ kauppaa tästä eteenpäin. $k$:s kauppa ($1 \le k \le Q$) tarkoittaa erikoistuotteiden kuljettamista kaupungista $A_k$ kaupunkiin $B_k$ joidenkin teiden ja kaupunkien kautta. Kuitenkin vain osavaltio $S_{A_k}$ ja osavaltio $S_{B_k}$ (tai vain osavaltio $S_{A_k}$, kun $S_{A_k} = S_{B_k}$) tekevät yhteistyötä tässä kaupassa, ja jos reitti kulkee minkä tahansa näihin osavaltioihin kuulumattoman kaupungin kautta, erikoistuotteet varastetaan.

Johtaja K haluaa selvittää, onko olemassa kuljetusreittiä, jolla kauppa voidaan suorittaa ilman, että erikoistuotteet varastetaan. Kun annetaan kaupunkien ja teiden sijoittelu sekä tiedot osavaltioista ja kaupoista, kirjoita ohjelma, joka määrittää jokaiselle kaupalle, voidaanko erikoistuotteet toimittaa turvallisesti perille.

Rajoitukset

• $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$).
• Jokaiselle $l$ ($1 \le l \le K$) on olemassa $j$ ($1 \le j \le N$) siten, että $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$).
• Kaikki syötteen arvot ovat kokonaislukuja.

Osatehtävät

1. ($5$ pistettä) $N \le 1\,000$, $M \le 1\,000$, $Q \le 1\,000$.
2. ($11$ pistettä) Kaikki osavaltioon $l$ ($1 \le l \le K$) kuuluvat kaupungit voivat kulkea toistensa välillä käyttäen vain teitä ja osavaltioon $l$ kuuluvia kaupunkeja.
3. ($42$ pistettä) $N \le 80\,000$, $M \le 80\,000$, $Q \le 80\,000$.
4. ($42$ pistettä) Ei lisärajoituksia.

Syöte

Syöte annetaan vakiosyötteestä seuraavassa muodossa:

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

Tuloste

Tulosta vakiotulosteeseen $Q$ riviä. Tulosta $k$:nnelle riville ($1 \le k \le Q$) 1, jos erikoistuotteet on mahdollista toimittaa perille $k$:nnessa kaupassa, ja 0, jos se on mahdotonta.

Esimerkki 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$. kauppa on erikoistuotteiden kuljettaminen kaupungista $1$ kaupunkiin $2$ kulkien vain osavaltioon $1$ tai osavaltioon $2$ kuuluvien kaupunkien kautta. Kuljetus reittiä kaupunki $1$ → kaupunki $2$ täyttää ehdon, joten tulostetaan 1.
• $2$. kauppa on erikoistuotteiden kuljettaminen kaupungista $1$ kaupunkiin $3$ kulkien vain osavaltioon $1$ kuuluvien kaupunkien kautta. Koska ehdon täyttävää kuljetusreittiä ei ole olemassa, tulostetaan 0.
• $3$. kauppa on erikoistuotteiden kuljettaminen kaupungista $1$ kaupunkiin $4$ kulkien vain osavaltioon $1$ tai osavaltioon $2$ kuuluvien kaupunkien kautta. Kuljetus reittiä kaupunki $1$ → kaupunki $2$ → kaupunki $3$ → kaupunki $4$ täyttää ehdon, joten tulostetaan 1.

Tämä esimerkkisyöte täyttää osatehtävien $1, 3, 4$ rajoitukset.

Esimerkki 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

Tämä esimerkkisyöte täyttää osatehtävien $1, 3, 4$ rajoitukset.

Esimerkki 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

Tämä esimerkkisyöte täyttää kaikkien osatehtävien rajoitukset.

Esimerkki 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

Tämä esimerkkisyöte täyttää osatehtävien $1, 3, 4$ rajoitukset.