Morpheus i-a oferit lui Neo o alegere între pastila roșie, care simbolizează adevărul dureros și pastila albastră, care simbolizează pacea în ignoranță. Pentru că are probleme la mansardă, Neo a luat pastilele și le-a înghițit pe ambele. Ca urmare, Matrix-ul a început să implodeze și cei doi nu îl pot repara decât prin colaborare.

Cerința

Cele două pastile ale lui Morpheus sunt formate din N1, respectiv N2 molecule, cu N1-1, respectiv N2-1 legături între ele. Molecula principală este cea cu eticheta 1 în cazul ambelor pastile. Se garantează că există o singură modalitate de a parcurge legăturile din orice moleculă în oricare alta. Ei bine, Morpheus are Q întrebări de forma a b, unde vrea să afle dacă subpastila a din pastila roșie este identică structural cu subpastila b din pastila albastră. Ajută-i pe Neo si Morpheus să repare această catastrofă și îți vor mulțumi cu 100 de puncte!

Date de intrare

Pe prima linie se vor afla numerele N1, N2 si Q, reprezentând numărul moleculelor din pastila roșie, numărul moleculelor din pastila albastră, respectiv numărul de întrebări.

Pe următoarele N1-1 linii se vor afla câte două numere a și b, reprezentând o legătură între molecula a și molecula b din pastila roșie.

Pe următoarele N2-1 linii se vor afla câte două numere a și b, reprezentând o legătură între molecula a și molecula b din pastila albastră.

Pe următoarele Q linii se vor afla câte două numere a și b, reprezentând o întrebare de a lui Morpheus.

Date de ieșire

Se va afișa un șir binar de lungime Q, bitul i (0 ≤ i < Q, numărând din stânga) reprezentând răspunsul pentru a i-a întrebare.

Restricții și precizări

• Se recomandă folosirea fastio
• 1 ≤ N1, N2, Q ≤ 100.000
• povestea enunțului nu este canonică
• Morpheus îți dă două numere care crede că îți vor fi de folos: 666.013, 1.000.000.007

Exemplu:

Intrare

9 7 6
1 2
1 3
2 4
2 5
3 6
3 7
6 8
6 9
1 2
1 3
3 4
3 5
4 7
4 6
3 3
1 1
2 4
6 4
2 1
3 6

Ieșire

101100

Explicație

Structura pastilelor este ilustrată în imaginea de mai jos.