An vielen Orten in Russland schneit es im Winter. Russland hat $N$ Städte, die von $0$ bis $N-1$ nummeriert sind, und $N-1$ Straßen, die von $0$ bis $N-2$ nummeriert sind. Straße $i$ ($0 \le i \le N-2$) verbindet zwei verschiedene Städte $A_i,B_i$ ($0 \le A_i < B_i \le N-1$) in beiden Richtungen. Zwischen je zwei verschiedenen Städten kann man über einige Straßen reisen.

Die Schneefallsituation jeder Straße ändert sich von Tag zu Tag. An jedem Tag schneit es auf jeder Straße entweder oder es schneit dort nicht. Innerhalb eines Tages ändert sich die Schneefallsituation nicht.

Anya und Boris arbeiten bei der russischen Verkehrsbehörde. Anya gehört zur Abteilung für die Verwaltung der Straßeninformationen, Boris zur Abteilung für die Beantwortung von Bürgeranfragen. Die Bürger fragen, wie viele Straßen, auf denen es schneit, man mindestens benutzen muss, um von der Hauptstadt, Stadt $0$, zu einer bestimmten anderen Stadt zu gelangen. Normalerweise tauscht sich Boris nach dem Erhalt einer Anfrage mit Anya aus und antwortet dann dem Bürger.

Nun findet in Russland eine Weltmeisterschaft im Programmieren statt, die $Q$ Tage dauert. Während des Wettbewerbs wird eine Überlastung der Kommunikationsleitungen erwartet, sodass Anya und Boris nur schwer direkt miteinander kommunizieren können. Daher beschließen sie, folgendermaßen zu kommunizieren.

• Anya erhält zu Beginn jedes Tages die Schneefallinformationen dieses Tages und sendet Daten an einen Zwischenserver.
• Wenn Boris eine Bürgeranfrage erhält, beantwortet er sie durch Kommunikation mit dem Zwischenserver.

Für diese Kommunikation gelten jedoch die folgenden Einschränkungen.

• Der Zwischenserver hat eine Kapazität von $L=1\,000$ Bits. Anya kann dort höchstens $L$ Bits an Informationen speichern.
• Alle auf dem Zwischenserver gespeicherten Daten werden zu Beginn jedes Tages mit $0$ initialisiert.
• Mit jeder Kommunikation mit dem Zwischenserver kann Boris genau ein von ihm bestimmtes Bit lesen.
• Zur Beantwortung jeder einzelnen Anfrage darf Boris höchstens 20-mal mit dem Zwischenserver kommunizieren.

Da du mit dem Leiter der Verkehrsbehörde bekannt bist, sollst du eine Strategie für Anya und Boris entwickeln.

Aufgabe

Schreibe Programme, die Strategien für Anya und Boris implementieren, mit denen Bürgeranfragen korrekt beantwortet werden können.

Implementierungsdetails

Du musst zwei Dateien in derselben Programmiersprache einreichen.

Die erste Datei heißt Anya.c oder Anya.cpp. Sie implementiert Anyas Strategie und muss die folgenden beiden Routinen implementieren. Das Programm muss Anyalib.h einbinden.

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

Diese Funktion wird für jeden Testfall genau einmal aufgerufen.

• Der Parameter N gibt die Anzahl der Städte an.
• Die Parameter A[] und B[] sind jeweils Folgen der Länge $N-1$, die die Straßenverbindungen beschreiben. Die ganzzahligen Elemente A[i] und B[i] ($0 \le i \le N-2$) geben an, dass Straße $i$ die Städte A[i] und B[i] in beiden Richtungen verbindet. Sie erfüllen $0 \le \texttt{A[i]} < \texttt{B[i]} \le N-1$.

void Anya(int C[])

Diese Funktion wird nach InitAnya insgesamt $Q$-mal aufgerufen. Sie entspricht der Entscheidung Anyas, welche Bitfolge sie auf dem Zwischenserver speichert, nachdem die Schneefallinformationen zu Beginn eines Tages aktualisiert wurden.

• Der Parameter C[] ist eine Folge der Länge $N-1$, die die Schneefallinformationen der Straßen beschreibt. Das Element C[i] ($0 \le i \le N-2$) ist eine ganze Zahl $0$ oder $1$ und beschreibt den Schneefall auf Straße $i$: C[i] = 1 bedeutet, dass es dort schneit, und C[i] = 0, dass es dort nicht schneit.

Innerhalb von Anya darf die folgende Funktion aufgerufen werden.

void Save(int place, int bit)

Diese Funktion entspricht dem Speichern eines Bits auf dem Zwischenserver durch Anya.

• Der Parameter place gibt die Position an, an der das Bit gespeichert wird. Er muss eine ganze Zahl zwischen $0$ und $L-1$ einschließlich sein. Ein Aufruf mit einem Wert außerhalb dieses Bereichs führt zu Falsche Antwort [1]. Außerdem darf Save innerhalb eines einzelnen Aufrufs von Anya nicht zweimal oder öfter mit demselben Parameter place aufgerufen werden. Bei zwei Aufrufen mit demselben Parameter lautet das Ergebnis Falsche Antwort [2].
• Der ganzzahlige Parameter bit gibt das zu speichernde Bit an und muss $0$ oder $1$ sein. Ein Aufruf mit einem anderen Wert führt zu Falsche Antwort [3].

Nach dem Aufruf von Save enthält das Bit an Position place des Zwischenservers den Wert bit.

Wird ein Aufruf von Save als falsch bewertet, endet das Programm sofort.

Unmittelbar vor jedem Aufruf von Anya werden immer alle Bits des Zwischenservers mit $0$ initialisiert. An Positionen, an denen nicht mit Save gespeichert wurde, steht daher nach dem Ende von Anya der Wert $0$.

Die zweite Datei heißt Boris.c oder Boris.cpp. Sie implementiert Boris' Strategie und muss die folgenden beiden Routinen implementieren. Das Programm muss Borislib.h einbinden.

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

Diese Funktion wird für jeden Testfall genau einmal aufgerufen.

• Der Parameter N gibt die Anzahl der Städte an.
• Die Parameter A[] und B[] sind jeweils Folgen der Länge $N-1$, die die Straßenverbindungen beschreiben. Die ganzzahligen Elemente A[i] und B[i] ($0 \le i \le N-2$) geben an, dass Straße $i$ die Städte A[i] und B[i] in beiden Richtungen verbindet. Sie erfüllen $0 \le \texttt{A[i]} < \texttt{B[i]} \le N-1$.

int Boris(int city)

Diese Funktion wird nach InitBoris mehrfach aufgerufen. Sie entspricht Boris' Vorgehen bei einer Bürgeranfrage.

• Der Parameter city beschreibt die Bürgeranfrage. Er ist eine ganze Zahl zwischen $1$ und $N-1$ einschließlich. Der Bürger fragt nach der Mindestanzahl an Straßen, auf denen es schneit, die er auf dem Weg von Stadt $0$ nach Stadt city benutzen muss.
• Boris muss als Antwort eine ganze Zahl zwischen $0$ und $N-1$ einschließlich zurückgeben. Ein Wert außerhalb dieses Bereichs führt zu Falsche Antwort [4]. Ist die Antwort nicht korrekt, lautet das Ergebnis Falsche Antwort [7].

Innerhalb von Boris darf die folgende Funktion aufgerufen werden.

int Ask(int place)

Diese Funktion entspricht dem Lesen eines Bits vom Zwischenserver durch Boris.

• Der Parameter place gibt die Position des zu lesenden Bits an. Er muss eine ganze Zahl zwischen $0$ und $L-1$ einschließlich sein. Ein Aufruf mit einem Wert außerhalb dieses Bereichs führt zu Falsche Antwort [5].

Der Rückgabewert von Ask ist der Inhalt des Bits an Position place auf dem Zwischenserver, also $0$ oder $1$. Innerhalb jedes einzelnen Aufrufs von Boris darf Ask höchstens 20-mal aufgerufen werden. Mehr als 20 Aufrufe führen zu Falsche Antwort [6].

Wird ein Aufruf von Ask als falsch bewertet, endet das Programm sofort.

Bewertungsablauf

Die Bewertung erfolgt wie folgt. Sobald eine falsche Antwort festgestellt wird, endet das Programm.

1. Um die Straßeninformationen zu übergeben, werden InitAnya und InitBoris jeweils einmal in dieser Reihenfolge aufgerufen.

2. Für $i=1,\ldots,Q$ werden der Reihe nach folgende Schritte ausgeführt:

   a. Anya wird genau einmal aufgerufen. Dies entspricht Anyas Entscheidung über die zu speichernde Bitfolge nach der Aktualisierung der Schneefallinformationen zu Beginn des Tages.

   b. Boris wird $D_i$-mal aufgerufen. Dabei ist $D_i$ die Anzahl der Bürgeranfragen am $i$-ten Tag. Der Parameter des $j$-ten Aufrufs ($1 \le j \le D_i$) ist $R_{ij}$ ($1 \le R_{ij} \le N-1$). Stimmt der Rückgabewert von Boris dabei nicht mit der Mindestanzahl schneebetroffener Straßen überein, die man auf dem Weg von Stadt $0$ nach Stadt $R_{ij}$ benutzen muss, ist die Antwort falsch.

3. Wurde nie eine falsche Antwort festgestellt, ist die Lösung korrekt.

Wichtige Hinweise

• Laufzeit und Speicherverbrauch werden für die Schritte (1) und (2) des Bewertungsablaufs gemessen. Bei einer korrekten Lösung wird in Schritt (2) Anya insgesamt $Q$-mal und Boris insgesamt $D_1+\cdots+D_Q$-mal aufgerufen.
• Anya und Boris können die Werte $D_1,\ldots,D_Q$ nicht erfahren.
• Boris erhält keine Informationen darüber, wann Anya die auf dem Zwischenserver gespeicherten Daten aktualisiert hat.
• Du darfst weitere Routinen für den internen Gebrauch implementieren und globale Variablen deklarieren. Die beiden eingereichten Programme werden jedoch mit dem Bewertungsprogramm zu einer ausführbaren Datei gelinkt. Deshalb müssen alle globalen Variablen und internen Routinen jeder Datei (außer InitAnya, Anya, InitBoris, Boris) mit static deklariert werden, um Konflikte mit anderen Dateien zu vermeiden. Bei der Bewertung wird das Programm in zwei Prozessen ausgeführt, einem für Anya und einem für Boris. Die beiden Seiten können daher keine globalen Variablen teilen.
• Deine Lösung darf in keiner Weise mit der Standardeingabe, der Standardausgabe oder anderen Dateien kommunizieren.

Kompilierung und Ausführung

In dem Archiv, das du von der Wettbewerbsseite herunterladen kannst, befindet sich ein Beispielbewertungsprogramm zum Testen deiner Programme. Das Archiv enthält auch Beispiele für die einzureichenden Dateien.

Das Beispielbewertungsprogramm besteht aus einer Datei namens grader.c oder grader.cpp. Wenn deine Programme Anya.c und Boris.c beziehungsweise Anya.cpp und Boris.cpp heißen, führe zum Testen folgende Befehle aus.

• Für C

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

• Für C++

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

Bei erfolgreicher Kompilierung wird eine ausführbare Datei namens grader erzeugt.

Beachte, dass das tatsächliche Bewertungsprogramm vom Beispielbewertungsprogramm abweicht. Das Beispielbewertungsprogramm wird als einzelner Prozess gestartet. Es liest Eingaben von der Standardeingabe und schreibt Ergebnisse auf die Standardausgabe.

Überblick über das Beispielbewertungsprogramm

Das Beispielbewertungsprogramm ruft die Funktionen gemäß dem Bewertungsablauf auf.

Beachte den folgenden Unterschied zum tatsächlichen Bewertungsprogramm.

• Das Beispielbewertungsprogramm prüft nicht auf Falsche Antwort [7], sondern gibt stattdessen für jede Anfrage den Rückgabewert von Boris aus.

Eingabe des Beispielbewertungsprogramms

Das Beispielbewertungsprogramm liest folgende Daten von der Standardeingabe.

• Die erste Zeile enthält die ganze Zahl $N$, die Anzahl der Städte.
• Die $(i+1)$-te der folgenden $N-1$ Zeilen ($0 \le i \le N-2$) enthält die durch ein Leerzeichen getrennten ganzen Zahlen $A_i,B_i$. Dies bedeutet, dass Straße $i$ die Städte $A_i$ und $B_i$ in beiden Richtungen verbindet.
• Die nächste Zeile enthält die ganze Zahl $Q$. Dies bedeutet, dass der Wettbewerb $Q$ Tage dauert.
• Die $i$-te der folgenden $Q$ Zeilen ($1 \le i \le Q$) enthält eine Zeichenkette $S_i$ der Länge $N-1$ und $D_i+1$ ganze Zahlen, jeweils durch Leerzeichen getrennt. $S_i$ beschreibt die Schneefallinformationen am $i$-ten Tag. Ist das $(j+1)$-te Zeichen von links ($0 \le j \le N-2$) 1, schneit es auf Straße $j$; bei 0 schneit es dort nicht. Die erste der folgenden $D_i+1$ ganzen Zahlen ist $D_i$. Die weiteren $D_i$ Zahlen sind $R_{i1},\ldots,R_{iD_i}$. Dies bedeutet, dass sich die $j$-te Anfrage ($1 \le j \le D_i$) am $i$-ten Tag auf die Mindestanzahl schneebetroffener Straßen auf dem Weg von Stadt $0$ nach Stadt $R_{ij}$ bezieht.

Ausgabe des Beispielbewertungsprogramms

Das Beispielbewertungsprogramm gibt folgende Informationen auf der Standardausgabe aus (die Anführungszeichen werden nicht tatsächlich ausgegeben).

• Wird während der Programmausführung eine falsche Antwort festgestellt, wird die Art des Fehlers beispielsweise als Wrong Answer [1] ausgegeben und die Ausführung beendet.
• Wurde in keinem der $D_i$ Aufrufe von Boris nach dem $i$-ten Aufruf von Anya ($1 \le i \le Q$) eine falsche Antwort festgestellt, werden anschließend $D_i$ durch Leerzeichen getrennte ganze Zahlen in einer Zeile ausgegeben. Die $j$-te Zahl ($1 \le j \le D_i$) ist der Rückgabewert von Boris mit dem Parameter $R_{ij}$.

Erfüllt das ausgeführte Programm mehrere Bedingungen für eine falsche Antwort, wird nur eine dieser Fehlerarten angezeigt.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

• $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$.
• Zwischen je zwei verschiedenen Städten kann man über einige Straßen reisen.

Teilaufgaben

Teilaufgabe 1 [15 Punkte]

• Es gilt $N \le 20$.

Teilaufgabe 2 [5 Punkte]

• Es gilt $N \le 100$.

Teilaufgabe 3 [35 Punkte]

Es gelten die folgenden Bedingungen.

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

Teilaufgabe 4 [45 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Im Folgenden stehen eine Beispieleingabe für das Beispielbewertungsprogramm und die entsprechenden Funktionsaufrufe.

Eingabe 1

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

Beispielaufrufe

Aufruf, darin ausgeführte Aufrufe und Rückgabewerte (kein bedeutet kein Rückgabewert):

InitAnya(...) -> kein
InitBoris(...) -> kein
Anya(...)
    Save(0,1) -> kein
    Save(1,0) -> kein
    Save(500,1) -> kein
  -> kein
Boris(2)
    Ask(0) -> 1
    Ask(1) -> 0
    Ask(2) -> 0
  -> 1
Boris(4) -> 0
Boris(3) -> 2
Anya(...) -> kein
Boris(4)
    Ask(0) -> 0
  -> 2

Beachte, dass die Funktionsaufrufe in diesem Beispiel nicht unbedingt sinnvoll sein müssen.

Die an InitAnya(...), InitBoris(...) sowie den ersten und zweiten Aufruf von Anya(...) übergebenen Parameter lauten dabei wie folgt:

InitAnya(...):
N = 5
A = {0, 1, 1, 2}
B = {1, 2, 4, 3}

InitBoris(...):
N = 5
A = {0, 1, 1, 2}
B = {1, 2, 4, 3}

Anya(...), erster Aufruf:
C = {0, 1, 0, 1}

Anya(...), zweiter Aufruf:
C = {1, 1, 1, 0}