Det finns $N$ öar där bävrar bor, numrerade från $0$ till $N-1$. Dessa öar är sammanbundna med $N-1$ dubbelriktade broar. Det är möjligt att resa mellan vilka två öar som helst genom att använda några broar. För varje ö finns det högst 18 broar som är direkt anslutna till den. Varje ö bebos av en bäver.

Ibland samlas några bävrar på en ö för att hålla ett möte. När exakt tre bävrar möts samlas de på följande ö:

Den ö som minimerar det totala antalet broar som de tre bävrarna färdas över när de samlas (en sådan ö existerar entydigt).

Observera att denna ö kan sammanfalla med en ö där en av de tre bävrarna bor.

Du är intresserad av hur de $N$ öarna är sammanbundna med broar. Du kan inte åka och kontrollera öarna direkt, så du tänker ge några instruktioner till bävrarna. En instruktion ser ut som följer:

• Du anger tre öar $u$, $v$ och $w$ ($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$), och låter bävrarna som bor på öarna $u$, $v$ och $w$ hålla ett möte.
• Då får du se vilken ö de tre bävrarna samlas på.

Du vill fastställa hur öarna är sammanbundna med så få instruktioner som möjligt.

Skriv ett program som, givet antalet öar, genom att kommunicera med bävrarna fastställer hur öarna är sammanbundna.

Implementeringsdetaljer

Du ska skicka in en fil.

Namnet på filen är meetings.cpp. Den ska implementera följande funktion. Programmet ska inkludera meetings.h.

• void Solve(int N)

Denna funktion anropas exakt en gång för varje testfall.

• Parametern N representerar $N$, antalet öar.

Ditt program kan anropa följande funktioner.

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

Denna funktion returnerar, för indexen på de tre öar du anger, indexet på den ö där bävrarna som bor där samlas för ett möte.

• Du anger indexen $u$, $v$ och $w$ för de tre öarna via parametrarna u, v respektive w. Dessa måste uppfylla $0 \le u \le N-1$, $0 \le v \le N-1$, $0 \le w \le N-1$, $u \ne v$, $u \ne w$ och $v \ne w$. Annars bedöms ditt program som Wrong Answer [1].

• Funktionen Query får inte anropas mer än $100\,000$ gånger. Annars bedöms ditt program som Wrong Answer [2].

• void Bridge(int u, int v)

Med hjälp av denna funktion svarar du hur öarna är sammanbundna med broar.

• Parametrarna u och v representerar att öarna $u$ och $v$ är direkt sammanbundna med en bro.
• Om $0 \le u < v \le N-1$ inte gäller bedöms ditt program som Wrong Answer [3].
• Om öarna $u$ och $v$ inte är direkt sammanbundna med en bro bedöms ditt program som Wrong Answer [4].
• Om funktionen Bridge anropas med samma parametrar u och v flera gånger bedöms ditt program som Wrong Answer [5].
• Eftersom det finns $N-1$ broar måste funktionen Bridge anropas exakt $N-1$ gånger. Om antalet anrop till funktionen Bridge inte är $N-1$ i slutet av körningen av funktionen Solve bedöms ditt program som Wrong Answer [6].

Viktiga anmärkningar

• Ditt program får implementera andra funktioner för internt bruk eller använda globala variabler.
• Ditt program får inte använda standard in eller standard ut. Ditt program får inte kommunicera med andra filer på något sätt. Ditt program får dock skriva ut felsökningsinformation till standard error.

Kompilering och testkörning

Du kan ladda ner en arkivfil från tävlingens webbsida som innehåller exempelbedömaren för att testa ditt program. Arkivfilen innehåller också en exempelkällkodsfil för ditt program.

Exempelbedömaren är filen grader.cpp. För att testa ditt program, lägg grader.cpp, meetings.cpp och meetings.h i samma katalog och kör följande kommando för att kompilera dina program.

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

När kompileringen lyckas skapas den körbara filen grader.

Observera att den faktiska bedömaren skiljer sig från exempelbedömaren. Exempelbedömaren körs som en enda process som läser indata från standard in och skriver resultaten till standard ut.

Indata för exempelbedömaren

Exempelbedömaren läser följande data från standard in.

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

$A_i$ och $B_i$ ($0 \le i \le N-2$) representerar att öarna $A_i$ och $B_i$ är direkt sammanbundna med en bro.

Utdata för exempelbedömaren

När programmet avslutas normalt skriver exempelbedömaren följande information till standard ut (citattecken för tydlighetens skull).

• Om ditt program bedöms som korrekt skriver den ut antalet anrop till funktionen Query som “Accepted: 100”.
• Om ditt program bedöms som Wrong Answer skriver den ut typen som “Wrong Answer [1]”.

Om ditt program uppfyller villkoren för flera typer av Wrong Answer rapporterar exempelbedömaren endast en av dem.

Begränsningar

Se avsnittet “Indata för exempelbedömaren” för definitionen av $A_i$ och $B_i$.

• $3 \le N \le 2\,000$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• Det är möjligt att resa mellan vilka två öar som helst genom att använda några broar.
• För varje ö finns det högst 18 broar som är direkt anslutna till den.

Deluppgifter

1. (7 poäng) $N \le 7$.
2. (10 poäng) $N \le 50$.
3. (12 poäng) $N \le 300$.

4. (71 poäng) Inga ytterligare begränsningar.

5. För Deluppgift 1, 2 och 3 får du full poäng om ditt program är korrekt för alla testfall i deluppgiften.

6. För Deluppgift 4, om ditt program är korrekt för alla testfall, blir din poäng följande, där $X$ är det maximala antalet anrop till funktionen Query för ett testfall:

   • 49 poäng om $40\,000 < X \le 100\,000$, och
   • 71 poäng om $X \le 40\,000$.

Exempelkommunikation

Här är ett exempel på indata för exempelbedömaren och motsvarande funktionsanrop.

Indata 1

5
0 1
0 2
1 3
1 4

Exempelanrop