Diese Aufgabe ist interaktiv.

An diesem Festtag voller süßer Düfte steht die Zubereitung des krönenden Desserts, der Milch mit doppelter Haut, vor einer letzten Schwierigkeit.

Als beliebtestes Dessert des Ladens muss eine perfekte Milch mit doppelter Haut die obere Kuchenschicht und die untere Puddingschicht vollkommen vereinen. In diesem magischen Flohkönigreich sind die Energien der beiden Dessertschichten miteinander verflochten und in einem komplexen Netz von Städten verborgen.

Die beiden erfahrenen Dessertmeister des Ladens, dacake8 und dapudding8, haben beschlossen, dich auf die Probe zu stellen. Sie haben Kuchen und Pudding auf den Straßen zwischen den Städten versteckt. Nur indem du sie befragst und eine Stadt genau bestimmst, die mit dem Hauptgeschäft, in dem du dich befindest (Stadt $1$), verbunden ist und auf deren Verbindungsstraße ein Dessert versteckt ist, kannst du dieses krönende Dessert, die Milch mit doppelter Haut, erfolgreich vollenden!

Es gibt $n$ Städte, und zwischen jedem Paar von Städten gibt es eine Straße. Es gibt $n-1$ Stücke Kuchen; das $i$-te Stück liegt auf der Straße zwischen den Städten $u_{i,1}$ und $v_{i,1}$. Es gibt $n-1$ Portionen Pudding; die $i$-te Portion liegt auf der Straße zwischen den Städten $u_{i,2}$ und $v_{i,2}$. Die Straßen mit Kuchen und die Straßen mit Pudding bilden jeweils einen Baum.

Anfangs kennst du die genauen Positionen von Kuchen und Pudding nicht. Du kannst dacake8 und dapudding8 höchstens $\min(1000,\frac{n\times(n-1)}{2})$ Anfragen stellen:

• Du fragst dacake8 und dapudding8 nach den Städten $u$ und $v$. Anfangs ist die Multimenge $S$ leer.

  • dacake8 startet in Stadt $u$, folgt dem Pfad aus Straßen mit Kuchen bis zur Stadt $v$ und fügt die Nummern der dabei besuchten Städte zur Multimenge $S$ hinzu.
  • dapudding8 startet in Stadt $u$, folgt dem Pfad aus Straßen mit Pudding bis zur Stadt $v$ und fügt die Nummern der dabei besuchten Städte zur Multimenge $S$ hinzu.
• Die Interaktionsbibliothek gibt die Multimenge $S$ zurück.

Du befindest dich in Stadt $1$. Nach den Anfragen musst du eine Stadt $u$ angeben, sodass auf der Straße zwischen Stadt $1$ und Stadt $u$ eine Art Dessert liegt.

dacake8 und dapudding8 wollen es dir nicht unnötig schwer machen und garantieren, dass die Positionen von Kuchen und Pudding bereits vor den Anfragen festgelegt sind. Das bedeutet: Die Interaktionsbibliothek ist nicht adaptiv.

Implementierungsdetails

Du brauchst keine Funktion main zu implementieren und sollst es auch nicht tun.

Du musst in der Quelldatei milk.cpp die Headerdatei milk.h einbinden und die folgenden beiden Funktionen implementieren:

void init(int c, int t);

• $c,t$ bezeichnen die Nummer der Teilaufgabe bzw. die Anzahl der Testfälle. $id=0$ bedeutet, dass diese Testdatei ein Beispiel ist.
• Für jede Testdatei ruft die Interaktionsbibliothek diese Funktion beim Start des Programms genau einmal auf.

int find(int c, int n);

• $c,n$ bezeichnen die Nummer der Teilaufgabe bzw. die Anzahl der Städte.
• Diese Funktion muss eine positive ganze Zahl $u$ zurückgeben, die eine Stadt $u$ angibt, sodass auf der Straße zwischen Stadt $1$ und Stadt $u$ eine Art Dessert liegt.
• Für jede Testdatei ruft die Interaktionsbibliothek diese Funktion genau $t$-mal auf.

Du kannst durch Aufruf der folgenden Funktion eine Anfrage stellen:

std::vector<int>query(int u, int v);

• $u,v$ geben die beiden Städte $u$ und $v$ an.
• Du musst sicherstellen, dass $1\le u,v\le n$ und $u\ne v$ gelten.
• Diese Funktion gibt die Multimenge $S$ zurück; ihre genaue Bedeutung steht in der Aufgabenstellung.
• Hat die Multimenge $S$ die Größe $m$, so gelten $1\le S_i\le n$ und $S_0\le S_1\le \ldots \le S_{m-1}$.
• Du musst sicherstellen, dass diese Funktion bei jedem Aufruf von find durch die Interaktionsbibliothek höchstens $1000$-mal aufgerufen wird.

Testen des Programms

Lege milk.cpp, milk.h und die Datei grader.cpp aus dem Anhang in dasselbe Verzeichnis und kompiliere sie mit C++17:

g++ grader.cpp milk.cpp -o milk -O2 -std=c++17
./milk < ex_milk1.in

Für die durch das Kompilieren erzeugte ausführbare Datei milk gilt:

Die erste Eingabezeile der Interaktionsbibliothek enthält zwei nichtnegative ganze Zahlen $id,t$, die die Nummer der Testdatei bzw. die Anzahl der Testfälle bezeichnen.

Für jeden Testfall enthält die erste Zeile eine positive ganze Zahl $n$, die die Anzahl der Städte angibt. Jede der Zeilen $2\sim n$ enthält zwei positive ganze Zahlen $u_{i,1}$, $v_{i,1}$; jede der nächsten $n-1$ Zeilen enthält zwei weitere positive ganze Zahlen $u_{i,2}$, $v_{i,2}$.

Wenn bei allen $t$ Aufrufen von find die Antworten korrekt sind, gibt die Interaktionsbibliothek in der ersten Zeile Correct! und in der zweiten Zeile Max queries used: Q aus. Dabei bezeichnet $Q$ die maximale Anzahl von Aufrufen von query über alle Testfälle. Ist mindestens eine Antwort falsch, wird Wrong answer. ausgegeben; ist ein Schnittstellenaufruf ungültig, wird zusätzlich der Grund für den Fehler auf der Standardfehlerausgabe ausgegeben.

Beispiele

Eingabe 1

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

Ausgabe 1

Correct!
Max queries used: 28

Hinweis

Beachte, dass die endgültigen Testdaten die Beispiele nicht enthalten.

In den Abbildungen bedeutet eine rote Kante, dass auf der Straße zwischen den beiden Städten ein Stück Kuchen liegt; eine blaue Kante bedeutet, dass auf der Straße zwischen den beiden Städten eine Portion Pudding liegt.

Für den ersten Testfall haben die von den Straßen mit Kuchen bzw. Pudding gebildeten Bäume die folgende Form:

Für den zweiten Testfall haben die von den Straßen mit Kuchen bzw. Pudding gebildeten Bäume die folgende Form:

Für den dritten Testfall gilt: Auf einer Straße können auch gleichzeitig Kuchen und Pudding liegen.

Beschränkungen

Besondere Eigenschaft $\text{A}$: Die Positionen von Kuchen und Pudding werden rein zufällig erzeugt.

Besondere Eigenschaft $\text{B}$: Es ist garantiert, dass es genau eine mögliche Antwort gibt.

Besondere Eigenschaft $\text{C}$: Werden beide Bäume, die von den Straßen mit Kuchen bzw. Pudding gebildet werden, in Stadt $1$ verwurzelt und von jeder Stadt gerichtete Kanten zu ihrer Elternstadt in jedem der beiden Bäume gezogen, so bildet der entstehende gerichtete Graph einen DAG.

Besondere Eigenschaft $\text{D}$: Werden beide Bäume, die von den Straßen mit Kuchen bzw. Pudding gebildet werden, in Stadt $2$ verwurzelt und von jeder Stadt gerichtete Kanten zu ihrer Elternstadt in jedem der beiden Bäume gezogen, so bildet der entstehende gerichtete Graph einen DAG.

Besondere Eigenschaft $\text{E}$: Die Positionen des Puddings werden rein zufällig erzeugt. Die Positionen des Kuchens hängen nicht von den Positionen des Puddings ab.

Besondere Eigenschaft $\text{F}$: Die beiden Bäume, die von den Straßen mit Kuchen bzw. Pudding gebildet werden, sind zwei Ketten, die beide Stadt $1$ als Anfang haben.

In dieser Aufgabe bedeutet die zufällige Erzeugung eines Baums die Erzeugung mittels einer zufälligen Prufer-Sequenz.

Teilaufgaben

Wenn die von find zurückgegebene Antwort falsch ist oder die Parameter von query ungültig sind, beträgt der Bewertungsfaktor für diese Testdatei $0$.

Für die Teilaufgaben $1,2,3$ gilt: Wenn die Anzahl der Anfragen $\frac{n\times(n-1)}{2}$ überschreitet, beträgt der Bewertungsfaktor für diese Testdatei $0$; andernfalls beträgt er $1$.

Für die Teilaufgaben $4\sim 15$ sei $Q$ die maximale Anzahl von Aufrufen von query über alle Testfälle. Der Bewertungsfaktor $f(Q)$ wird anhand der folgenden Tabelle berechnet:

Die endgültige Punktzahl einer Testdatei ist ihre Punktzahl multipliziert mit dem Bewertungsfaktor. Nach den UOJ-Regeln für reellwertige Punktzahlen werden drei Nachkommastellen beibehalten.

Zeitlimit: $20\ \mathrm{s}$.

Speicherlimit: $512\ \mathrm{MiB}$.