Lýsing á verkefni

Í Bandaríkjum JOI eru $N$ borgir númeraðar frá $1$ til $N$, og $M$ vegir númeraðir frá $1$ til $M$. Vegur $i$ ($1 \le i \le M$) tengir borg $U_i$ og borg $V_i$ í báðar áttir.

Bandaríki JOI skiptast í $K$ fylki númeruð frá $1$ til $K$. Borg $j$ ($1 \le j \le N$) tilheyrir fylki $S_j$. Auk þess inniheldur hvert fylki að minnsta kosti $1$ borg.

Framkvæmdastjórinn K, iðnaðarráðherra Bandaríkja JOI, áætlar að framkvæma $Q$ viðskipti héðan í frá. $k$-tu viðskiptin ($1 \le k \le Q$) felast í því að flytja sérvörur frá borg $A_k$ til borgar $B_k$ um einhverja vegi og borgir. Hins vegar taka aðeins fylki $S_{A_k}$ og fylki $S_{B_k}$ (eða aðeins fylki $S_{A_k}$ þegar $S_{A_k} = S_{B_k}$) þátt í þessum viðskiptum, og ef leiðin liggur um einhverja borg sem tilheyrir ekki þessum fylkjum verður sérvörunum stolið.

Framkvæmdastjórinn K vill kanna hvort til sé flutningsleið til að framkvæma viðskiptin án þess að sérvörunum verði stolið. Gefið skipulag borga og vega, ásamt upplýsingum um fylkin og viðskiptin, skrifið forrit til að ákvarða fyrir hver viðskipti hvort hægt sé að koma sérvörunum örugglega til skila.

Takmarkanir

• $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$).
• Fyrir sérhvert $l$ ($1 \le l \le K$) er til $j$ ($1 \le j \le N$) þannig að $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$).
• Öll inntaksgildi eru heiltölur.

Undirverkefni

1. ($5$ stig) $N \le 1\,000$, $M \le 1\,000$, $Q \le 1\,000$.
2. ($11$ stig) Allar borgir sem tilheyra fylki $l$ ($1 \le l \le K$) geta ferðast sín á milli með því að fara eingöngu um vegi og borgir sem tilheyra fylki $l$.
3. ($42$ stig) $N \le 80\,000$, $M \le 80\,000$, $Q \le 80\,000$.
4. ($42$ stig) Engar viðbótartakmarkanir.

Inntak

Inntak er gefið úr staðalinntaki á eftirfarandi sniði:

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

Úttak

Skrifið $Q$ línur í staðalúttak. Á $k$-tu línu ($1 \le k \le Q$), skrifið 1 ef hægt er að koma sérvörunum til skila í $k$-tu viðskiptunum, en 0 ef það er ómögulegt.

Dæmi 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$. viðskiptin felast í því að flytja sérvörur frá borg $1$ til borgar $2$ með því að fara eingöngu um borgir sem tilheyra fylki $1$ eða fylki $2$. Flutningur eftir borg $1$ → borg $2$ uppfyllir skilyrðið, svo við skrifum 1.
• $2$. viðskiptin felast í því að flytja sérvörur frá borg $1$ til borgar $3$ með því að fara eingöngu um borgir sem tilheyra fylki $1$. Þar sem engin flutningsleið sem uppfyllir skilyrðið er til, skrifum við 0.
• $3$. viðskiptin felast í því að flytja sérvörur frá borg $1$ til borgar $4$ með því að fara eingöngu um borgir sem tilheyra fylki $1$ eða fylki $2$. Flutningur eftir borg $1$ → borg $2$ → borg $3$ → borg $4$ uppfyllir skilyrðið, svo við skrifum 1.

Þetta sýnidæmi uppfyllir takmarkanir undirverkefna $1, 3, 4$.

Dæmi 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

Þetta sýnidæmi uppfyllir takmarkanir undirverkefna $1, 3, 4$.

Dæmi 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

Þetta sýnidæmi uppfyllir takmarkanir allra undirverkefna.

Dæmi 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

Þetta sýnidæmi uppfyllir takmarkanir undirverkefna $1, 3, 4$.