Det finnes $N$ øyer der bevere bor, nummerert fra $0$ til $N-1$. Disse øyene er bundet sammen av $N-1$ toveis broer. Det er mulig å reise mellom hvilke som helst øyer ved å bruke noen broer. For hver øy er det høyst 18 broer som er direkte koblet til den. Hver øy er bebodd av en bever.

Noen ganger samles noen bevere på en øy for å holde et møte. Når nøyaktig tre bevere møtes, samles de på følgende øy:

Øya som minimerer det totale antallet broer de tre beverne reiser over når de samles (en slik øy eksisterer entydig).

Merk at denne øya kan sammenfalle med en øy der en av de tre beverne bor.

Du er interessert i hvordan de $N$ øyene er bundet sammen av broer. Du kan ikke dra og sjekke øyene direkte, så du har tenkt å gi noen instruksjoner til beverne. En instruksjon er som følger:

• Du oppgir tre øyer $u$, $v$ og $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$), og lar beverne som bor på øyene $u$, $v$ og $w$ holde et møte.
• Deretter får du se hvilken øy de tre beverne samles på.

Du ønsker å finne ut hvordan øyene er bundet sammen med få instruksjoner.

Skriv et program som, gitt antall øyer, ved å kommunisere med beverne finner ut hvordan øyene er bundet sammen.

Implementeringsdetaljer

Du må sende inn én fil.

Navnet på filen er meetings.cpp. Den skal implementere følgende funksjon. Programmet skal inkludere meetings.h.

• void Solve(int N)

Denne funksjonen kalles nøyaktig én gang for hvert testtilfelle.

• Parameteren N representerer $N$, antall øyer.

Programmet ditt kan kalle følgende funksjoner.

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

Denne funksjonen returnerer, for indeksene til de tre øyene du oppgir, indeksen til øya der beverne som bor der samles til et møte.

• Du oppgir indeksene $u$, $v$ og $w$ til de tre øyene via parametrene u, v og w, henholdsvis. Disse må oppfylle $0 \le u \le N-1$, $0 \le v \le N-1$, $0 \le w \le N-1$, $u \ne v$, $u \ne w$ og $v \ne w$. Ellers blir programmet ditt bedømt som Wrong Answer [1].

• Funksjonen Query må ikke kalles mer enn $100\,000$ ganger. Ellers blir programmet ditt bedømt som Wrong Answer [2].

• void Bridge(int u, int v)

Ved å bruke denne funksjonen svarer du hvordan øyene er bundet sammen av broer.

• Parametrene u og v representerer at øyene $u$ og $v$ er direkte koblet sammen med en bro.
• Hvis $0 \le u < v \le N-1$ ikke gjelder, blir programmet ditt bedømt som Wrong Answer [3].
• Hvis øyene $u$ og $v$ ikke er direkte koblet sammen med en bro, blir programmet ditt bedømt som Wrong Answer [4].
• Hvis funksjonen Bridge kalles med de samme parametrene u og v flere ganger, blir programmet ditt bedømt som Wrong Answer [5].
• Siden det er $N-1$ broer, må funksjonen Bridge kalles nøyaktig $N-1$ ganger. Hvis antall kall til funksjonen Bridge ikke er $N-1$ ved slutten av kjøringen av funksjonen Solve, blir programmet ditt bedømt som Wrong Answer [6].

Viktige merknader

• Programmet ditt kan implementere andre funksjoner til internt bruk, eller bruke globale variabler.
• Programmet ditt skal ikke bruke standard inndata eller standard utdata. Programmet ditt skal ikke kommunisere med andre filer på noen måte. Programmet ditt kan imidlertid skrive ut feilsøkingsinformasjon til standard feilutdata (standard error).

Kompilering og testkjøring

Du kan laste ned en arkivfil fra konkurransens nettside som inneholder eksempelbedømmeren for å teste programmet ditt. Arkivfilen inneholder også en eksempelkildekodefil for programmet ditt.

Eksempelbedømmeren er filen grader.cpp. For å teste programmet ditt, legg grader.cpp, meetings.cpp og meetings.h i samme mappe, og kjør følgende kommando for å kompilere programmene dine.

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

Når kompileringen lykkes, genereres den kjørbare filen grader.

Merk at den faktiske bedømmeren er forskjellig fra eksempelbedømmeren. Eksempelbedømmeren vil bli kjørt som én enkelt prosess, som leser inndata fra standard inndata og skriver resultatene til standard utdata.

Inndata for eksempelbedømmeren

Eksempelbedømmeren leser følgende data fra standard inndata.

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

$A_i$ og $B_i$ ($0 \le i \le N-2$) representerer at øyene $A_i$ og $B_i$ er direkte koblet sammen med en bro.

Utdata for eksempelbedømmeren

Når programmet avsluttes normalt, skriver eksempelbedømmeren følgende informasjon til standard utdata (anførselstegn for tydelighetens skyld).

• Hvis programmet ditt bedømmes som riktig, skriver den ut antall kall til funksjonen Query som “Accepted: 100”.
• Hvis programmet ditt bedømmes som Wrong Answer, skriver den ut typen som “Wrong Answer [1]”.

Hvis programmet ditt oppfyller kravene til flere typer Wrong Answer, rapporterer eksempelbedømmeren bare én av dem.

Begrensninger

Se avsnittet “Inndata for eksempelbedømmeren” for definisjonen av $A_i$ og $B_i$.

• $3 \le N \le 2\,000$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• Det er mulig å reise mellom hvilke som helst øyer ved å bruke noen broer.
• For hver øy er det høyst 18 broer som er direkte koblet til den.

Deloppgaver

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

4. (71 poeng) Ingen ytterligere begrensninger.

5. For Deloppgave 1, 2 og 3 får du full poengsum hvis programmet ditt er riktig for alle testtilfellene i deloppgaven.

6. For Deloppgave 4, hvis programmet ditt er riktig for alle testtilfellene, vil poengsummen din være som følger, der $X$ er det maksimale antallet kall til funksjonen Query for et testtilfelle:

   • 49 poeng hvis $40\,000 < X \le 100\,000$, og
   • 71 poeng hvis $X \le 40\,000$.

Eksempelkommunikasjon

Her er et eksempel på inndata for eksempelbedømmeren og tilhørende funksjonskall.

Inndata 1

5
0 1
0 2
1 3
1 4

Eksempelkall