I mange deler av Russland snør det om vinteren. Det er $N$ byer i Russland, nummerert fra $0$ til $N-1$. Det er $N-1$ veier, nummerert fra $0$ til $N-2$. Vei $i$ ($0 \le i \le N-2$) forbinder to ulike byer $A_i$ og $B_i$ ($0 \le A_i < B_i \le N-1$) i begge retninger. Det er mulig å reise mellom hvilke som helst to ulike byer i Russland ved å følge en sekvens av veier.

Snøforholdene på hver vei endrer seg fra dag til dag. På en gitt dag er hver vei enten snødekt eller ikke snødekt. Snøforholdene på en vei endrer seg ikke i løpet av én enkelt dag.

Anya og Boris jobber i det russiske samferdselsdepartementet. Anya jobber i avdelingen for veiinformasjon, og Boris jobber i avdelingen som svarer på spørsmål fra innbyggerne. Et spørsmål fra en innbygger er: «Hva er det minste antallet snødekte veier jeg må kjøre gjennom for å reise fra hovedstaden, by 0, til en bestemt annen by?» Boris svarer vanligvis innbyggerne etter å ha mottatt et spørsmål og kommunisert med Anya.

Nylig arrangeres en verdenskonkurranse i programmering i Russland over $Q$ dager. Under konkurransen forventes det at kommunikasjonslinjene vil være overbelastet, noe som gjør det vanskelig for Anya og Boris å kommunisere direkte. Derfor har Anya og Boris bestemt seg for å kommunisere på følgende måte:

• På begynnelsen av hver dag mottar Anya informasjonen om snødekte veier for den dagen og sender data til en reléserver.
• Når Boris mottar et spørsmål fra en innbygger, svarer han på det ved å kommunisere med reléserveren.

Det er imidlertid følgende begrensninger på kommunikasjonen mellom Anya og Boris:

• Kapasiteten til reléserveren er $L = 1000$ biter. Anya kan lagre høyst $L$ biter med informasjon på reléserveren.
• Dataene som er lagret på reléserveren, nullstilles til bare 0-ere på begynnelsen av hver dag.
• Boris kan lese 1 spesifisert bit med informasjon ved å interagere med reléserveren én gang.
• For å svare på et spørsmål kan Boris interagere med reléserveren høyst 20 ganger per spørsmål.

Du, en bekjent av direktøren for samferdselsdepartementet, har blitt bedt om å utarbeide en strategi for Anya og Boris.

Skriv et program som implementerer en strategi for Anya og Boris som kan svare riktig på innbyggernes spørsmål.

Implementasjonsdetaljer

Du må sende inn to filer i samme programmeringsspråk.

Den første filen heter Anya.c eller Anya.cpp. Denne filen implementerer Anyas strategi og må implementere følgende to rutiner. Programmet må inkludere Anyalib.h.

• void InitAnya(int N, int A[], int B[]) Denne funksjonen kalles nøyaktig én gang for hvert testtilfelle.

  • Argumentet N representerer antallet byer.
  • Argumentene A[] og B[] er tabeller med lengde $N-1$, som representerer informasjonen om veiforbindelsene. Elementene A[i] og B[i] ($0 \le i \le N-2$) er heltall som representerer at vei $i$ forbinder byene A[i] og B[i] i begge retninger, og tilfredsstiller $0 \le A[i] < B[i] \le N-1$.

• void Anya(int C[]) Denne funksjonen kalles $Q$ ganger etter at InitAnya er kalt. Denne funksjonen tilsvarer at Anya bestemmer bitstrengen som skal lagres på reléserveren etter at informasjonen om snødekte veier er oppdatert på begynnelsen av dagen.

  • Argumentet C[] er en tabell med lengde $N-1$, som representerer informasjonen om snødekte veier. Elementet C[i] ($0 \le i \le N-2$) er et heltall på 0 eller 1, der C[i] = 1 betyr at vei $i$ er snødekt, og C[i] = 0 betyr at vei $i$ ikke er snødekt.

Inne i funksjonen Anya kan du kalle følgende funksjon:

• void Save(int place, int bit) Denne funksjonen representerer operasjonen der Anya lagrer en bit på reléserveren.

  • Argumentet place representerer posisjonen der biten skal skrives. place må være et heltall mellom $0$ og $L-1$ (inkludert). Hvis en verdi utenfor dette intervallet oppgis, bedømmes det som Wrong Answer [1]. I hvert kall til funksjonen Anya kan du heller ikke kalle denne funksjonen med samme place-argument mer enn én gang. Hvis den kalles to ganger med samme argument, bedømmes det som Wrong Answer [2].
  • Argumentet bit er et heltall som representerer biten som skal skrives, som må være 0 eller 1. Hvis en annen verdi oppgis, bedømmes det som Wrong Answer [3].

Etter Save-kallet blir innholdet i den place-te biten på reléserveren bit. Hvis et Save-kall bedømmes som Wrong Answer, avsluttes programmet der og da.

Umiddelbart før funksjonen Anya kalles, blir bitene på reléserveren alltid satt til bare 0-ere. Det vil si at på slutten av funksjonen Anya vil posisjoner der det ikke ble utført noen lagringsoperasjon med funksjonen Save, inneholde 0.

Den andre filen heter Boris.c eller Boris.cpp. Denne filen implementerer Boris' strategi og må implementere følgende to rutiner. Programmet må inkludere Borislib.h.

• void InitBoris(int N, int A[], int B[]) Denne funksjonen kalles nøyaktig én gang for hvert testtilfelle.

  • Argumentet N representerer antallet byer.
  • Argumentene A[] og B[] er tabeller med lengde $N-1$, som representerer informasjonen om veiforbindelsene. Elementene A[i] og B[i] ($0 \le i \le N-2$) er heltall som representerer at vei $i$ forbinder byene A[i] og B[i] i begge retninger, og tilfredsstiller $0 \le A[i] < B[i] \le N-1$.

• int Boris(int city) Denne funksjonen kalles flere ganger etter at InitBoris er kalt. Denne funksjonen tilsvarer Boris' handling som svar på et spørsmål fra en innbygger.

  • Argumentet city representerer innbyggerens spørsmål. city er et heltall mellom $1$ og $N-1$ (inkludert). Dette representerer at innbyggeren spør om det minste antallet snødekte veier vedkommende må kjøre gjennom for å reise fra by 0 til city.
  • Funksjonen Boris må returnere et heltall mellom $0$ og $N-1$ (inkludert), som er svaret på innbyggerens spørsmål. Hvis et heltall utenfor dette intervallet returneres, bedømmes det som Wrong Answer [4]. Hvis svaret er feil, bedømmes det som Wrong Answer [7].

Inne i funksjonen Boris kan du kalle følgende funksjon:

• int Ask(int place) Denne funksjonen representerer operasjonen der Boris leser en bit fra reléserveren.

  • Argumentet place representerer posisjonen biten skal leses fra. place må være et heltall mellom $0$ og $L-1$ (inkludert). Hvis en verdi utenfor dette intervallet oppgis, bedømmes det som Wrong Answer [5].

  Returverdien til funksjonen Ask er et heltall som representerer innholdet i den place-te biten på reléserveren, som er 0 eller 1. Videre kan funksjonen Ask kalles høyst 20 ganger i hvert kall til funksjonen Boris. Hvis den kalles mer enn 20 ganger, bedømmes det som Wrong Answer [6].

Hvis et Ask-kall bedømmes som Wrong Answer, avsluttes programmet der og da.

Begrensninger

• $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$.
• Det er mulig å reise mellom hvilke som helst to ulike byer ved å følge en sekvens av veier.

Deloppgaver

1. (15 poeng) $N \le 20$.
2. (5 poeng) $N \le 100$.
3. (35 poeng) $A_i = i$ og $B_i = i + 1$ for alle $0 \le i \le N-2$.
4. (45 poeng) Ingen ytterligere begrensninger.

Eksempler

Inndata 1

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

Utdata 1

1 0 2
2

Merk

Eksempelet ovenfor viser interaksjonsflyten. Den første linjen i inndataene er $N=5$. De neste 4 linjene definerer kantene. Neste linje er $Q=2$. De påfølgende linjene beskriver de snødekte veiene og spørringene for hver dag. Utdataene viser svarene gitt av Boris for spørringene på hver dag.