W wielu miejscach Rosji zimą pada śnieg. W Rosji jest $N$ miast ponumerowanych od $0$ do $N-1$ oraz $N-1$ dróg ponumerowanych od $0$ do $N-2$. Droga $i$ ($0 \le i \le N-2$) łączy dwukierunkowo dwa różne miasta $A_i,B_i$ ($0 \le A_i < B_i \le N-1$). Między dowolnymi dwoma różnymi miastami można podróżować, przejeżdżając przez pewne drogi.

Warunki opadów śniegu na każdej drodze zmieniają się z dnia na dzień. Każdego dnia na każdej drodze albo pada śnieg, albo nie pada. W ciągu jednego dnia sytuacja się nie zmienia.

Anya i Boris pracują w rosyjskim urzędzie transportu. Anya zajmuje się zarządzaniem informacjami o drogach, a Boris odpowiada na pytania mieszkańców. Mieszkańcy pytają, przez ile co najmniej dróg, na których pada śnieg, trzeba przejechać, aby dostać się ze stolicy Rosji, miasta $0$, do pewnego innego miasta. Zwykle po otrzymaniu pytania Boris kontaktuje się z Anyą, a następnie odpowiada mieszkańcowi.

W Rosji odbędą się teraz mistrzostwa świata w programowaniu, trwające $Q$ dni. Oczekuje się, że podczas zawodów łącza komunikacyjne będą przeciążone, co utrudni bezpośredni kontakt Anyi i Borisa. Postanowili więc komunikować się w następujący sposób:

• Na początku dnia Anya otrzymuje informacje o opadach śniegu w tym dniu i przesyła dane na serwer pośredniczący.
• Po otrzymaniu pytania od mieszkańca Boris odpowiada, komunikując się z serwerem pośredniczącym.

Ich komunikację ograniczają jednak następujące warunki:

• Pojemność serwera pośredniczącego wynosi $L=1\,000$ bitów. Anya może zapisać na nim najwyżej $L$ bitów informacji.
• Na początku każdego dnia wszystkie dane zapisane na serwerze są inicjalizowane zerami.
• Podczas jednej operacji komunikacji z serwerem Boris może odczytać jeden wskazany bit informacji.
• Aby odpowiedzieć na jedno pytanie, Boris może skomunikować się z serwerem najwyżej $20$ razy.

Ponieważ znasz dyrektora urzędu transportu, masz opracować strategię Anyi i Borisa.

Zadanie

Napisz programy implementujące strategie Anyi i Borisa, które pozwolą poprawnie odpowiadać na pytania mieszkańców.

Szczegóły implementacji

Musisz przesłać dwa pliki napisane w tym samym języku programowania.

Pierwszy plik ma nazwę Anya.c lub Anya.cpp. Implementuje strategię Anyi i musi zawierać dwie poniższe procedury. Program powinien dołączać Anyalib.h.

void InitAnya(int N, int A[], int B[])

Ta funkcja jest wywoływana dokładnie raz w każdym przypadku testowym.

• Argument $N$ oznacza liczbę miast.
• Argumenty A[] i B[] to ciągi długości $N-1$ opisujące połączenia dróg. Elementy $A[i]$ i $B[i]$ ($0 \le i \le N-2$) są liczbami całkowitymi oznaczającymi, że droga $i$ łączy dwukierunkowo miasta $A[i]$ i $B[i]$; spełniają $0 \le A[i] < B[i] \le N-1$.

void Anya(int C[])

Ta funkcja jest wywoływana $Q$ razy po wywołaniu InitAnya. Odpowiada wybraniu przez Anyę ciągu bitów do zapisania na serwerze pośredniczącym po aktualizacji informacji o opadach na drogach na początku dnia.

• Argument C[] to ciąg długości $N-1$ opisujący opady śniegu na drogach. Element $C[i]$ ($0 \le i \le N-2$) jest liczbą całkowitą $0$ lub $1$ opisującą sytuację na drodze $i$: C[i] = 1 oznacza, że pada tam śnieg, a C[i] = 0 — że nie pada.

W funkcji Anya można wywoływać następującą funkcję.

void Save(int place, int bit)

Ta funkcja odpowiada zapisaniu bitu przez Anyę na serwerze pośredniczącym.

• Argument place oznacza miejsce zapisu bitu i musi być liczbą całkowitą od $0$ do $L-1$. Wywołanie z wartością spoza tego zakresu powoduje Błędną odpowiedź [1]. Ponadto w jednym wywołaniu funkcji Anya nie można wywołać tej funkcji dwa lub więcej razy z tym samym argumentem place. Dwukrotne wywołanie z tym samym argumentem powoduje Błędną odpowiedź [2].
• Argument bit jest liczbą całkowitą oznaczającą zapisywany bit i musi wynosić $0$ lub $1$. Wywołanie z inną wartością powoduje Błędną odpowiedź [3].

Po wywołaniu Save bit serwera pośredniczącego na pozycji place ma wartość bit.

Jeśli wywołanie Save zostanie uznane za Błędną odpowiedź, program natychmiast się kończy.

Tuż przed każdym wywołaniem funkcji Anya wszystkie bity serwera pośredniczącego są zawsze zerowane. Innymi słowy, miejsca, w których nie wykonano zapisu funkcją Save, na końcu funkcji Anya zawierają $0$.

Drugi plik ma nazwę Boris.c lub Boris.cpp. Implementuje strategię Borisa i musi zawierać dwie poniższe procedury. Program powinien dołączać Borislib.h.

void InitBoris(int N, int A[], int B[])

Ta funkcja jest wywoływana dokładnie raz w każdym przypadku testowym.

• Argument $N$ oznacza liczbę miast.
• Argumenty A[] i B[] to ciągi długości $N-1$ opisujące połączenia dróg. Elementy $A[i]$ i $B[i]$ ($0 \le i \le N-2$) są liczbami całkowitymi oznaczającymi, że droga $i$ łączy dwukierunkowo miasta $A[i]$ i $B[i]$; spełniają $0 \le A[i] < B[i] \le N-1$.

int Boris(int city)

Ta funkcja jest wywoływana wielokrotnie po wywołaniu InitBoris. Odpowiada działaniu Borisa podczas odpowiadania na pytanie mieszkańca.

• Argument city opisuje pytanie mieszkańca. Jest liczbą całkowitą od $1$ do $N-1$. Mieszkaniec pyta, przez ile co najmniej dróg, na których pada śnieg, trzeba przejechać, aby dostać się z miasta $0$ do miasta city.
• Funkcja Boris musi zwrócić liczbę całkowitą od $0$ do $N-1$ będącą odpowiedzią na pytanie mieszkańca. Zwrócenie liczby spoza tego zakresu powoduje Błędną odpowiedź [4]. Niepoprawna odpowiedź powoduje Błędną odpowiedź [7].

W funkcji Boris można wywoływać następującą funkcję.

int Ask(int place)

Ta funkcja odpowiada odczytaniu przez Borisa bitu z serwera pośredniczącego.

• Argument place oznacza miejsce odczytu bitu i musi być liczbą całkowitą od $0$ do $L-1$. Wywołanie z wartością spoza tego zakresu powoduje Błędną odpowiedź [5].

Wartość zwracana przez Ask to liczba całkowita $0$ lub $1$ oznaczająca zawartość bitu serwera pośredniczącego na pozycji place. Funkcję Ask można wywołać najwyżej $20$ razy w każdym wywołaniu funkcji Boris. Przekroczenie $20$ wywołań powoduje Błędną odpowiedź [6].

Jeśli wywołanie Ask zostanie uznane za Błędną odpowiedź, program natychmiast się kończy.

Procedura oceniania

Ocenianie przebiega w następujący sposób. W przypadku Błędnej odpowiedzi program natychmiast się kończy.

1. Aby przekazać informacje o drogach, funkcje InitAnya i InitBoris są wywoływane po jednym razie, w tej kolejności.

2. Dla $i=1,\ldots,Q$ wykonywane są kolejno następujące operacje:

   • (a) Funkcja Anya jest wywoływana dokładnie raz. Odpowiada wybraniu przez Anyę ciągu bitów do zapisania na serwerze po aktualizacji informacji o opadach na drogach na początku dnia.
   • (b) Funkcja Boris jest wywoływana $D_i$ razy, gdzie $D_i$ to liczba pytań mieszkańców w dniu $i$. Argumentem wywołania $j$ ($1 \le j \le D_i$) jest $R_{ij}$ ($1 \le R_{ij} \le N-1$). Jeśli w wywołaniu $j$ wartość zwrócona przez Boris nie jest równa minimalnej liczbie dróg, na których pada śnieg i przez które trzeba przejechać z miasta $0$ do miasta $R_{ij}$, odpowiedź zostaje uznana za błędną.

3. Jeśli ani razu nie stwierdzono Błędnej odpowiedzi, rozwiązanie zostaje uznane za poprawne.

Ważne uwagi

• Czas wykonania i zużycie pamięci mierzone są w krokach (1) i (2) „Procedury oceniania”. W przypadku poprawnego rozwiązania w kroku (2) funkcja Anya jest wywoływana łącznie $Q$ razy, a Boris łącznie $D_1+\cdots+D_Q$ razy.
• Anya i Boris nie mogą poznać wartości $D_1,\ldots,D_Q$.
• Funkcja Boris nie otrzymuje informacji, kiedy funkcja Anya zaktualizowała dane zapisane na serwerze pośredniczącym.
• Można implementować inne procedury na użytek wewnętrzny i deklarować zmienne globalne. Oba przesłane programy zostaną jednak połączone z programem oceniającym w jeden plik wykonywalny, więc wszystkie zmienne globalne i procedury wewnętrzne w każdym pliku (z wyjątkiem InitAnya, Anya, InitBoris, Boris) trzeba zadeklarować jako static, aby uniknąć konfliktów z innymi plikami. Podczas oceniania program działa jako dwa procesy, po stronie Anyi i po stronie Borisa, więc nie mogą one współdzielić zmiennych globalnych programu.
• Rozwiązanie nie może w żaden sposób komunikować się ze standardowym wejściem, standardowym wyjściem ani innymi plikami.

Kompilacja i uruchamianie

Archiwum dostępne do pobrania ze strony zawodów zawiera przykładowy program oceniający służący do testowania rozwiązania. Zawiera również przykładowe pliki, które należy przesłać.

Przykładowy program oceniający składa się z jednego pliku: grader.c lub grader.cpp. Jeśli twoje programy to Anya.c i Boris.c albo Anya.cpp i Boris.cpp, uruchom następujące polecenia, aby je przetestować.

• Dla C

gcc -std=c11 -O2 -o grader grader.c Anya.c Boris.c -lm

• Dla C++

g++ -std=c++11 -O2 -o grader grader.cpp Anya.cpp Boris.cpp

Po udanej kompilacji zostanie utworzony plik wykonywalny grader.

Pamiętaj, że właściwy program oceniający różni się od przykładowego. Przykładowy program uruchamia się jako jeden proces, czyta dane ze standardowego wejścia i wypisuje wyniki na standardowe wyjście.

Opis przykładowego programu oceniającego

Przykładowy program oceniający wywołuje funkcje zgodnie z „Procedurą oceniania”.

Pamiętaj, że poniższy aspekt różni się od zachowania właściwego programu oceniającego.

• Przykładowy program oceniający nie sprawdza warunku Błędnej odpowiedzi [7]. Zamiast tego wypisuje wartość zwróconą przez funkcję Boris dla każdego pytania.

Wejście przykładowego programu oceniającego

Przykładowy program oceniający czyta następujące dane ze standardowego wejścia.

• Pierwszy wiersz zawiera liczbę całkowitą $N$ oznaczającą liczbę miast.
• Wiersz $i+1$ ($0 \le i \le N-2$) spośród kolejnych $N-1$ wierszy zawiera liczby całkowite $A_i,B_i$ oddzielone spacją. Oznaczają one, że droga $i$ łączy dwukierunkowo miasta $A_i$ i $B_i$.
• Następny wiersz zawiera liczbę całkowitą $Q$ oznaczającą, że zawody trwają $Q$ dni.
• Wiersz $i$ ($1 \le i \le Q$) spośród kolejnych $Q$ wierszy zawiera ciąg znaków $S_i$ długości $N-1$ oraz $D_i+1$ liczb całkowitych, oddzielonych spacjami. $S_i$ opisuje opady śniegu w dniu $i$: znak $j+1$ od lewej ($0 \le j \le N-2$) równy 1 oznacza, że na drodze $j$ pada śnieg, a 0 — że nie pada. Pierwsza z kolejnych $D_i+1$ liczb to $D_i$. Następne $D_i$ liczb to $R_{i1},\ldots,R_{iD_i}$. Oznacza to, że pytanie $j$ ($1 \le j \le D_i$) w dniu $i$ dotyczy minimalnej liczby dróg, na których pada śnieg i przez które trzeba przejechać z miasta $0$ do miasta $R_{ij}$.

Wyjście przykładowego programu oceniającego

Przykładowy program oceniający wypisuje na standardowe wyjście następujące informacje (cudzysłowy nie są wypisywane).

• Jeśli podczas działania programu zostanie stwierdzona Błędna odpowiedź, jej typ zostaje wypisany w postaci takiej jak Wrong Answer [1], a wykonywanie programu zostaje zakończone.
• Jeśli żadna z $D_i$ funkcji Boris wywołanych po wywołaniu Anya numer $i$ ($1 \le i \le Q$) nie spowoduje Błędnej odpowiedzi, w tym momencie w jednym wierszu zostaje wypisane $D_i$ liczb całkowitych oddzielonych spacjami. Liczba $j$ ($1 \le j \le D_i$) jest wartością zwróconą przez Boris z argumentem $R_{ij}$.

Jeśli uruchomiony program spełnia kilka warunków Błędnej odpowiedzi, wypisywany jest tylko jeden z tych typów.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki.

• $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+\cdots+D_Q \le 500$.
• Między dowolnymi dwoma różnymi miastami można podróżować, przejeżdżając przez pewne drogi.

Podzadania

Podzadanie 1 (15 punktów)

• $N \le 20$.

Podzadanie 2 (5 punktów)

• $N \le 100$.

Podzadanie 3 (35 punktów)

Spełnione są następujące warunki.

• $A_i=i$ ($0 \le i \le N-2$).
• $B_i=i+1$ ($0 \le i \le N-2$).

Podzadanie 4 (45 punktów)

Brak dodatkowych ograniczeń.

Przykład interakcji

Poniżej podano przykład wejścia dla przykładowego programu oceniającego i odpowiadające mu wywołania funkcji.

Wejście 1

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

Przykładowe wywołania procedur

Pamiętaj, że wywołania funkcji w tym przykładzie niekoniecznie są sensowne.

Argumenty przekazane do InitAnya(...), InitBoris(...) oraz pierwszego i drugiego wywołania Anya(...) są następujące: