Ci sono $N$ isole in cui vivono dei castori, numerate da $0$ a $N-1$. Queste isole sono collegate da $N-1$ ponti bidirezionali. È possibile viaggiare tra qualsiasi coppia di isole utilizzando alcuni ponti. Per ciascuna isola, ci sono al massimo 18 ponti direttamente collegati ad essa. Ogni isola è abitata da un castoro.

A volte, alcuni castori si radunano su un'isola per tenere un incontro. Quando si incontrano esattamente tre castori, si radunano sulla seguente isola:

L'isola che minimizza il numero totale di ponti attraversati dai tre castori per radunarsi (una tale isola esiste ed è unica).

Si noti che quest'isola può coincidere con un'isola in cui vive uno dei tre castori.

Sei interessato a sapere come sono collegate le $N$ isole tramite i ponti. Non puoi andare a controllare direttamente le isole, quindi impartirai alcune istruzioni ai castori. Un'istruzione è la seguente:

• Specifichi tre isole $u$, $v$ e $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$), e fai tenere un incontro ai castori che vivono sulle isole $u$, $v$ e $w$.
• Quindi, puoi vedere l'isola in cui si radunano i tre castori.

Vuoi determinare come sono collegate le isole con poche istruzioni.

Scrivi un programma che, dato il numero di isole, comunicando con i castori, determini come sono collegate le isole.

Dettagli implementativi

Devi inviare un solo file.

Il nome del file è meetings.cpp. Deve implementare la seguente funzione. Il programma deve includere meetings.h.

• void Solve(int N)

Questa funzione viene chiamata esattamente una volta per ciascun caso di test.

• Il parametro N rappresenta $N$, il numero di isole.

Il tuo programma può chiamare le seguenti funzioni.

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

Questa funzione restituisce, per gli indici delle tre isole specificate, l'indice dell'isola in cui i castori che vi abitano si radunano per un incontro.

• Specifichi gli indici $u$, $v$ e $w$ delle tre isole tramite i parametri u, v e w, rispettivamente. Questi devono soddisfare $0 \le u \le N-1$, $0 \le v \le N-1$, $0 \le w \le N-1$, $u \ne v$, $u \ne w$ e $v \ne w$. Altrimenti, il tuo programma viene giudicato come Wrong Answer [1].

• La funzione Query non deve essere chiamata più di $100\,000$ volte. Altrimenti, il tuo programma viene giudicato come Wrong Answer [2].

• void Bridge(int u, int v)

Usando questa funzione, comunichi come le isole sono collegate dai ponti.

• I parametri u e v indicano che le isole $u$ e $v$ sono direttamente collegate da un ponte.
• Se non vale $0 \le u < v \le N-1$, il tuo programma viene giudicato come Wrong Answer [3].
• Se le isole $u$ e $v$ non sono direttamente collegate da un ponte, il tuo programma viene giudicato come Wrong Answer [4].
• Se la funzione Bridge viene chiamata più volte con gli stessi parametri u e v, il tuo programma viene giudicato come Wrong Answer [5].
• Poiché ci sono $N-1$ ponti, la funzione Bridge deve essere chiamata esattamente $N-1$ volte. Se il numero di chiamate alla funzione Bridge non è $N-1$ al termine dell'esecuzione della funzione Solve, il tuo programma viene giudicato come Wrong Answer [6].

Avvertenze importanti

• Il tuo programma può implementare altre funzioni per uso interno o utilizzare variabili globali.
• Il tuo programma non deve usare lo standard input né lo standard output. Il tuo programma non deve comunicare con altri file con alcun metodo. Tuttavia, il tuo programma può scrivere informazioni di debug sullo standard error.

Compilazione e prova di esecuzione

Puoi scaricare dalla pagina web della gara un file archivio che contiene il grader di esempio per testare il tuo programma. L'archivio contiene anche un file sorgente di esempio del tuo programma.

Il grader di esempio è il file grader.cpp. Per testare il tuo programma, metti grader.cpp, meetings.cpp e meetings.h nella stessa directory ed esegui il comando seguente per compilare i tuoi programmi.

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

Quando la compilazione va a buon fine, viene generato il file eseguibile grader.

Si noti che il grader effettivo è diverso dal grader di esempio. Il grader di esempio verrà eseguito come un singolo processo, che leggerà i dati di input dallo standard input e scriverà i risultati sullo standard output.

Input per il grader di esempio

Il grader di esempio legge i seguenti dati dallo standard input.

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

$A_i$ e $B_i$ ($0 \le i \le N-2$) indicano che le isole $A_i$ e $B_i$ sono direttamente collegate da un ponte.

Output del grader di esempio

Quando il programma termina correttamente, il grader di esempio scrive le seguenti informazioni sullo standard output (virgolette per chiarezza).

• Se il tuo programma è giudicato corretto, scrive il numero di chiamate alla funzione Query come “Accepted: 100”.
• Se il tuo programma è giudicato come Wrong Answer, ne scrive il tipo come “Wrong Answer [1]”.

Se il tuo programma incorre in più tipi di Wrong Answer, il grader di esempio ne segnala solo uno.

Limiti

Fai riferimento alla sezione “Input per il grader di esempio” per la definizione di $A_i$ e $B_i$.

• $3 \le N \le 2\,000$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• È possibile viaggiare tra qualsiasi coppia di isole utilizzando alcuni ponti.
• Per ciascuna isola, ci sono al massimo 18 ponti direttamente collegati ad essa.

Sottoproblemi

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

4. (71 punti) Nessuna limitazione aggiuntiva.

5. Per i Sottoproblemi 1, 2 e 3, se il tuo programma è corretto per tutti i casi di test di un sottoproblema, ottieni il punteggio pieno.

6. Per il Sottoproblema 4, se il tuo programma è corretto per tutti i casi di test, il tuo punteggio sarà il seguente, dove $X$ è il numero massimo di chiamate alla funzione Query per un caso di test:

   • 49 punti se $40\,000 < X \le 100\,000$, e
   • 71 punti se $X \le 40\,000$.

Esempio di comunicazione

Ecco un input di esempio per il grader di esempio e le corrispondenti chiamate di funzione.

Input 1

5
0 1
0 2
1 3
1 4

Chiamate di esempio