Monissa osissa Venäjää sataa lunta talvella. Venäjällä on $N$ kaupunkia, jotka on numeroitu $0$:sta $N-1$:een. Lisäksi on $N-1$ tietä, jotka on numeroitu $0$:sta $N-2$:een. Tie $i$ ($0 \le i \le N-2$) yhdistää kaksi eri kaupunkia $A_i$ ja $B_i$ ($0 \le A_i < B_i \le N-1$) molempiin suuntiin. Minkä tahansa kahden eri kaupungin välillä Venäjällä on mahdollista matkustaa kulkemalla jotakin teiden jonoa pitkin.

Kunkin tien lumitilanne vaihtelee päivästä toiseen. Minä tahansa päivänä jokainen tie on joko luminen tai lumeton. Tien lumitilanne ei muutu yhden päivän aikana.

Anya ja Boris työskentelevät Venäjän liikenneministeriössä. Anya työskentelee tietietojen hallintaosastolla ja Boris työskentelee osastolla, joka vastaa kansalaisten kysymyksiin. Kansalaisen kysymys kuuluu: "Mikä on pienin määrä lumisia teitä, joiden kautta minun on kuljettava matkustaakseni pääkaupungista, kaupungista 0, tiettyyn toiseen kaupunkiin?" Boris vastaa tavallisesti kansalaisille saatuaan kysymyksen ja oltuaan yhteydessä Anyaan.

Äskettäin Venäjällä järjestetään $Q$ päivää kestävä ohjelmoinnin maailmanmestaruuskilpailu. Kilpailun aikana viestintälinjojen odotetaan ruuhkautuvan, mikä tekee Anyan ja Borisin suorasta yhteydenpidosta vaikeaa. Siksi Anya ja Boris ovat päättäneet viestiä seuraavalla tavalla:

• Kunkin päivän alussa Anya saa kyseisen päivän tiedot lumisista teistä ja lähettää dataa välityspalvelimelle (relay server).
• Kun Boris saa kysymyksen kansalaiselta, hän vastaa siihen viestimällä välityspalvelimen kanssa.

Anyan ja Borisin välisessä viestinnässä on kuitenkin seuraavat rajoitukset:

• Välityspalvelimen kapasiteetti on $L = 1000$ bittiä. Anya voi tallentaa välityspalvelimelle enintään $L$ bittiä tietoa.
• Välityspalvelimelle tallennettu data alustetaan pelkiksi 0-biteiksi kunkin päivän alussa.
• Boris voi lukea yhden määritetyn bitin tietoa olemalla kerran yhteydessä välityspalvelimeen.
• Vastatakseen kysymykseen Boris voi olla yhteydessä välityspalvelimeen enintään 20 kertaa kysymystä kohden.

Sinua, liikenneministeriön johtajan tuttavaa, on pyydetty kehittämään strategia Anyalle ja Borisille.

Kirjoita ohjelma, joka toteuttaa Anyalle ja Borisille strategian, jolla voidaan vastata oikein kansalaisten kysymyksiin.

Toteutuksen yksityiskohdat

Sinun tulee palauttaa kaksi samalla ohjelmointikielellä kirjoitettua tiedostoa.

Ensimmäisen tiedoston nimi on Anya.c tai Anya.cpp. Tämä tiedosto toteuttaa Anyan strategian, ja sen tulee toteuttaa seuraavat kaksi aliohjelmaa. Ohjelman on sisällytettävä otsikkotiedosto Anyalib.h.

• void InitAnya(int N, int A[], int B[]) Tätä funktiota kutsutaan täsmälleen kerran jokaiselle testitapaukselle.

  • Argumentti N ilmaisee kaupunkien lukumäärän.
  • Argumentit A[] ja B[] ovat pituudeltaan $N-1$ olevia taulukoita, jotka ilmaisevat teiden yhteystiedot. Alkiot A[i] ja B[i] ($0 \le i \le N-2$) ovat kokonaislukuja, jotka ilmaisevat, että tie $i$ yhdistää kaupungit A[i] ja B[i] molempiin suuntiin, ja ne toteuttavat ehdon $0 \le A[i] < B[i] \le N-1$.

• void Anya(int C[]) Tätä funktiota kutsutaan $Q$ kertaa sen jälkeen, kun InitAnya on kutsuttu. Tämä funktio vastaa tilannetta, jossa Anya päättää välityspalvelimelle tallennettavan bittijonon sen jälkeen, kun lumisten teiden tiedot on päivitetty päivän alussa.

  • Argumentti C[] on pituudeltaan $N-1$ oleva taulukko, joka ilmaisee lumisten teiden tiedot. Alkio C[i] ($0 \le i \le N-2$) on kokonaisluku 0 tai 1, missä C[i] = 1 tarkoittaa, että tie $i$ on luminen, ja C[i] = 0 tarkoittaa, että tie $i$ ei ole luminen.

Funktion Anya sisällä voit kutsua seuraavaa funktiota:

• void Save(int place, int bit) Tämä funktio kuvaa operaatiota, jossa Anya tallentaa bitin välityspalvelimelle.

  • Argumentti place ilmaisee kohdan, johon bitti kirjoitetaan. place-arvon on oltava kokonaisluku välillä $0$ ja $L-1$ (rajat mukaan lukien). Jos annetaan tämän välin ulkopuolinen arvo, tulokseksi tulee Wrong Answer [1]. Lisäksi kussakin funktion Anya kutsussa tätä funktiota ei saa kutsua samalla place-argumentilla useammin kuin kerran. Jos sitä kutsutaan kahdesti samalla argumentilla, tulokseksi tulee Wrong Answer [2].
  • Argumentti bit on kirjoitettavaa bittiä kuvaava kokonaisluku, jonka on oltava 0 tai 1. Jos annetaan jokin muu arvo, tulokseksi tulee Wrong Answer [3].

Save-kutsun jälkeen välityspalvelimen place-nnen bitin sisällöksi tulee bit. Jos Save-kutsu arvioidaan tulokseksi Wrong Answer, ohjelman suoritus päättyy välittömästi.

Juuri ennen funktion Anya kutsumista välityspalvelimen bitit alustetaan aina pelkiksi 0-biteiksi. Toisin sanoen funktion Anya päättyessä kohdissa, joihin ei suoritettu tallennusoperaatiota Save-funktiolla, on arvo 0.

Toisen tiedoston nimi on Boris.c tai Boris.cpp. Tämä tiedosto toteuttaa Borisin strategian, ja sen tulee toteuttaa seuraavat kaksi aliohjelmaa. Ohjelman on sisällytettävä otsikkotiedosto Borislib.h.

• void InitBoris(int N, int A[], int B[]) Tätä funktiota kutsutaan täsmälleen kerran jokaiselle testitapaukselle.

  • Argumentti N ilmaisee kaupunkien lukumäärän.
  • Argumentit A[] ja B[] ovat pituudeltaan $N-1$ olevia taulukoita, jotka ilmaisevat teiden yhteystiedot. Alkiot A[i] ja B[i] ($0 \le i \le N-2$) ovat kokonaislukuja, jotka ilmaisevat, että tie $i$ yhdistää kaupungit A[i] ja B[i] molempiin suuntiin, ja ne toteuttavat ehdon $0 \le A[i] < B[i] \le N-1$.

• int Boris(int city) Tätä funktiota kutsutaan useita kertoja sen jälkeen, kun InitBoris on kutsuttu. Tämä funktio vastaa Borisin toimintaa hänen vastatessaan kansalaisen kysymykseen.

  • Argumentti city ilmaisee kansalaisen kysymyksen. city on kokonaisluku välillä $1$ ja $N-1$ (rajat mukaan lukien). Tämä tarkoittaa, että kansalainen kysyy pienintä määrää lumisia teitä, joiden kautta hänen on kuljettava matkustaakseen kaupungista 0 kaupunkiin city.
  • Funktion Boris on palautettava kokonaisluku välillä $0$ ja $N-1$ (rajat mukaan lukien), mikä on vastaus kansalaisen kysymykseen. Jos palautetaan tämän välin ulkopuolinen kokonaisluku, tulokseksi tulee Wrong Answer [4]. Jos vastaus on väärin, tulokseksi tulee Wrong Answer [7].

Funktion Boris sisällä voit kutsua seuraavaa funktiota:

• int Ask(int place) Tämä funktio kuvaa operaatiota, jossa Boris lukee bitin välityspalvelimelta.

  • Argumentti place ilmaisee kohdan, josta bitti luetaan. place-arvon on oltava kokonaisluku välillä $0$ ja $L-1$ (rajat mukaan lukien). Jos annetaan tämän välin ulkopuolinen arvo, tulokseksi tulee Wrong Answer [5].

  Funktion Ask paluuarvo on kokonaisluku, joka ilmaisee välityspalvelimen place-nnen bitin sisällön, eli 0 tai 1. Lisäksi funktiota Ask saa kutsua enintään 20 kertaa kussakin funktion Boris kutsussa. Jos sitä kutsutaan yli 20 kertaa, tulokseksi tulee Wrong Answer [6].

Jos Ask-kutsu arvioidaan tulokseksi Wrong Answer, ohjelman suoritus päättyy välittömästi.

Rajoitukset

• $2 \le N \le 500$.
• $1 \le Q \le 500$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• $1 \le D_j$ ($1 \le j \le Q$).
• $D_1 + \dots + D_Q \le 500$.
• Minkä tahansa kahden eri kaupungin välillä on mahdollista matkustaa kulkemalla jotakin teiden jonoa pitkin.

Osatehtävät

1. (15 pistettä) $N \le 20$.
2. (5 pistettä) $N \le 100$.
3. (35 pistettä) $A_i = i$ ja $B_i = i + 1$ kaikilla $0 \le i \le N-2$.
4. (45 pistettä) Ei lisärajoituksia.

Esimerkit

Syöte 1

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

Tuloste 1

1 0 2
2

Huomautus

Yllä oleva esimerkki näyttää vuorovaikutuksen kulun. Syötteen ensimmäinen rivi on $N=5$. Seuraavat 4 riviä määrittelevät kaaret. Seuraava rivi on $Q=2$. Seuraavat rivit kuvaavat lumiset tiet ja kyselyt kullekin päivälle. Tuloste näyttää Borisin antamat vastaukset kunkin päivän kyselyihin.