Es gibt $N$ Inseln, auf denen Biber leben. Die Inseln sind von $0$ bis $N-1$ nummeriert und durch $N-1$ in beide Richtungen begehbare Brücken verbunden. Über diese Brücken kann man von jeder Insel zu jeder anderen gelangen. Mit jeder Insel sind höchstens $18$ Brücken direkt verbunden. Auf jeder Insel lebt ein Biber.

Manchmal versammeln sich einige Biber auf einer Insel, um ein Treffen abzuhalten. Wenn sich genau drei Biber treffen, versammeln sie sich auf der folgenden Insel:

Die Insel, für die die Gesamtzahl der Brücken, die die drei Biber auf dem Weg zum Treffen überqueren, minimal ist. (Eine solche Insel existiert eindeutig.)

Beachte, dass diese Insel mit der Wohninsel eines der drei Biber übereinstimmen kann.

Du möchtest herausfinden, wie die $N$ Inseln durch Brücken verbunden sind. Da du die Inseln nicht direkt aufsuchen und überprüfen kannst, wirst du den Bibern einige Anweisungen geben. Eine Anweisung sieht folgendermaßen aus:

• Du gibst drei Inseln $u$, $v$ und $w$ an ($0 \le u \le N-1$, $0 \le v \le N-1$, $0 \le w \le N-1$, $u \ne v$, $u \ne w$, $v \ne w$) und lässt die auf den Inseln $u$, $v$ und $w$ lebenden Biber ein Treffen abhalten.
• Anschließend kannst du sehen, auf welcher Insel sich die drei Biber versammeln.

Du möchtest mit wenigen Anweisungen bestimmen, wie die Inseln verbunden sind.

Schreibe ein Programm, das die Anzahl der Inseln erhält und durch Kommunikation mit den Bibern bestimmt, wie die Inseln verbunden sind.

Implementierungsdetails

Du musst eine Datei einreichen.

Die Datei heißt meetings.cpp. Sie soll die folgende Funktion implementieren. Das Programm soll meetings.h einbinden.

void Solve(int N)

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

• Der Parameter N gibt $N$, die Anzahl der Inseln, an.

Dein Programm kann die folgenden Funktionen aufrufen.

int Query(int u, int v, int w)

Diese Funktion erhält die von dir angegebenen Nummern dreier Inseln und gibt die Nummer der Insel zurück, auf der sich die dort lebenden Biber zu einem Treffen versammeln.

• Die Nummern $u$, $v$ und $w$ der drei Inseln werden jeweils über die Parameter u, v und w angegeben. Sie müssen $0 \le u \le N-1$, $0 \le v \le N-1$, $0 \le w \le N-1$, $u \ne v$, $u \ne w$ und $v \ne w$ erfüllen. Andernfalls wird dein Programm als Wrong Answer [1] bewertet.
• Die Funktion Query darf höchstens $100\,000$ Mal aufgerufen werden. Andernfalls wird dein Programm als Wrong Answer [2] bewertet.

void Bridge(int u, int v)

Mit dieser Funktion gibst du an, wie die Inseln durch Brücken verbunden sind.

• Die Parameter u und v geben an, dass die Inseln $u$ und $v$ direkt durch eine Brücke verbunden sind.
• Falls $0 \le u < v \le N-1$ nicht gilt, wird dein Programm als Wrong Answer [3] bewertet.
• Falls die Inseln $u$ und $v$ nicht direkt durch eine Brücke verbunden sind, wird dein Programm als Wrong Answer [4] bewertet.
• Falls die Funktion Bridge mehrmals mit denselben Parametern u und v aufgerufen wird, wird dein Programm als Wrong Answer [5] bewertet.
• Da es $N-1$ Brücken gibt, muss die Funktion Bridge genau $N-1$ Mal aufgerufen werden. Falls die Anzahl der Aufrufe von Bridge am Ende der Ausführung von Solve nicht $N-1$ beträgt, wird dein Programm als Wrong Answer [6] bewertet.

Wichtige Hinweise

• Dein Programm darf weitere Funktionen für den internen Gebrauch implementieren und globale Variablen verwenden.
• Dein Programm darf weder die Standardeingabe noch die Standardausgabe verwenden. Es darf auf keinerlei Weise mit anderen Dateien kommunizieren. Es darf jedoch Informationen zur Fehlersuche auf die Standardfehlerausgabe schreiben.

Kompilierung und Testlauf

Du kannst von der Wettbewerbswebseite eine Archivdatei herunterladen, die einen Beispielgrader zum Testen deines Programms enthält. Das Archiv enthält auch eine Beispieldatei mit Quellcode für dein Programm.

Der Beispielgrader befindet sich in der Datei grader.cpp. Um dein Programm zu testen, lege grader.cpp, meetings.cpp und meetings.h in dasselbe Verzeichnis und führe zum Kompilieren den folgenden Befehl aus.

g++ -std=gnu++14 -O2 -o grader grader.cpp meetings.cpp

Bei erfolgreicher Kompilierung wird die ausführbare Datei grader erzeugt.

Beachte, dass sich der tatsächliche Grader vom Beispielgrader unterscheidet. Der Beispielgrader läuft als einzelner Prozess, der die Eingabedaten von der Standardeingabe liest und die Ergebnisse auf die Standardausgabe schreibt.

Eingabe für den Beispielgrader

Der Beispielgrader liest die folgenden Daten von der Standardeingabe.

$$ \begin{array}{l} N\\ A_0\ B_0\\ \vdots\\ A_{N-2}\ B_{N-2} \end{array} $$

$A_i$ und $B_i$ ($0 \le i \le N-2$) geben an, dass die Inseln $A_i$ und $B_i$ direkt durch eine Brücke verbunden sind.

Ausgabe für den Beispielgrader

Wenn das Programm erfolgreich beendet wird, schreibt der Beispielgrader die folgenden Informationen auf die Standardausgabe (die Anführungszeichen dienen der Verdeutlichung).

• Wenn dein Programm als korrekt bewertet wird, gibt er die Anzahl der Aufrufe der Funktion Query in der Form „Accepted: 100“ aus.
• Wenn dein Programm als Wrong Answer bewertet wird, gibt er den Fehlertyp in der Form „Wrong Answer [1]“ aus.

Wenn dein Programm mehrere Arten von Wrong Answer verursacht, meldet der Beispielgrader nur eine davon.

Beschränkungen

Die Definition von $A_i$ und $B_i$ findest du im Abschnitt „Eingabe für den Beispielgrader“.

• $3 \le N \le 2\,000$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• Über die Brücken kann man von jeder Insel zu jeder anderen gelangen.
• Mit jeder Insel sind höchstens $18$ Brücken direkt verbunden.

Teilaufgaben

1. (7 Punkte) $N \le 7$.
2. (10 Punkte) $N \le 50$.
3. (12 Punkte) $N \le 300$.

4. (71 Punkte) Keine zusätzlichen Beschränkungen.

5. Für die Teilaufgaben 1, 2 und 3 erhältst du die volle Punktzahl, wenn dein Programm für alle Testfälle der jeweiligen Teilaufgabe korrekt ist.

6. Für Teilaufgabe 4 erhältst du bei korrekter Lösung aller Testfälle die folgende Punktzahl. Dabei ist $X$ die maximale Anzahl der Aufrufe der Funktion Query für einen Testfall.

   • $49$ Punkte, falls $40\,000 < X \le 100\,000$, und
   • $71$ Punkte, falls $X \le 40\,000$.

Beispiele

Hier sind eine Beispieleingabe für den Beispielgrader und die zugehörigen Funktionsaufrufe.

Eingabe 1

5
0 1
0 2
1 3
1 4

Beispielaufrufe