Istnieje $N$ wysp zamieszkanych przez bobry, ponumerowanych od $0$ do $N-1$. Wyspy te są połączone $N-1$ dwukierunkowymi mostami. Między dowolnymi wyspami można przemieszczać się, korzystając z mostów. Z każdą wyspą połączonych jest bezpośrednio co najwyżej $18$ mostów. Na każdej wyspie mieszka jeden bóbr.

Czasami bobry zbierają się na jednej wyspie, aby odbyć spotkanie. Gdy spotykają się dokładnie trzy bobry, zbierają się na następującej wyspie:

Wyspie, która minimalizuje łączną liczbę mostów, przez które muszą przejść te trzy bobry, aby się spotkać (taka wyspa istnieje i jest wyznaczona jednoznacznie).

Zauważ, że może to być wyspa, na której mieszka jeden z tych trzech bobrów.

Interesuje Cię sposób połączenia $N$ wysp mostami. Nie możesz osobiście sprawdzić wysp, więc zamierzasz wydawać bobrom polecenia. Polecenie wygląda następująco:

• Wskazujesz trzy wyspy $u$, $v$ i $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$) i prosisz bobry mieszkające na wyspach $u$, $v$ i $w$ o odbycie spotkania.
• Następnie poznajesz wyspę, na której zebrały się te trzy bobry.

Chcesz ustalić sposób połączenia wysp, wydając niewiele poleceń.

Napisz program, który, znając liczbę wysp i komunikując się z bobrami, ustali sposób połączenia wysp.

Szczegóły implementacji

Należy przesłać jeden plik.

Plik powinien nazywać się meetings.cpp. Powinien implementować poniższą funkcję. Program powinien dołączać plik meetings.h.

• void Solve(int N)

  Ta funkcja jest wywoływana dokładnie raz dla każdego przypadku testowego.

  • Parametr N oznacza $N$, czyli liczbę wysp.

  Twój program może wywoływać następujące funkcje.

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

    Dla wskazanych indeksów trzech wysp funkcja zwraca indeks wyspy, na której bobry mieszkające na tych wyspach zbierają się na spotkanie.

    • Indeksy $u$, $v$ i $w$ trzech wysp przekazuje się odpowiednio przez parametry u, v i w. Muszą one spełniać $0\le u\le N-1$, $0\le v\le N-1$, $0\le w\le N-1$, $u\ne v$, $u\ne w$ i $v\ne w$. W przeciwnym razie program otrzyma wynik Wrong Answer [1].
    • Funkcji Query nie wolno wywołać więcej niż $100\,000$ razy. W przeciwnym razie program otrzyma wynik Wrong Answer [2].

  • void Bridge(int u, int v)

    Za pomocą tej funkcji podajesz sposób połączenia wysp mostami.

    • Parametry u i v oznaczają, że wyspy $u$ i $v$ są bezpośrednio połączone mostem.
    • Jeżeli warunek $0\le u<v\le N-1$ nie jest spełniony, program otrzyma wynik Wrong Answer [3].
    • Jeżeli wyspy $u$ i $v$ nie są bezpośrednio połączone mostem, program otrzyma wynik Wrong Answer [4].
    • Jeżeli funkcja Bridge zostanie wielokrotnie wywołana z tymi samymi parametrami u i v, program otrzyma wynik Wrong Answer [5].
    • Ponieważ istnieje $N-1$ mostów, funkcję Bridge należy wywołać dokładnie $N-1$ razy. Jeżeli w chwili zakończenia wykonywania funkcji Solve liczba wywołań funkcji Bridge nie wynosi $N-1$, program otrzyma wynik Wrong Answer [6].

Ważne uwagi

• Twój program może implementować inne funkcje do użytku wewnętrznego lub korzystać ze zmiennych globalnych.
• Twój program nie powinien używać standardowego wejścia ani standardowego wyjścia. Nie powinien też w żaden sposób komunikować się z innymi plikami. Może jednak wypisywać informacje diagnostyczne na standardowe wyjście błędów.

Kompilacja i uruchomienie testowe

Ze strony konkursu można pobrać archiwum zawierające przykładowy program oceniający służący do testowania Twojego programu. Archiwum zawiera także przykładowy plik źródłowy Twojego programu.

Przykładowy program oceniający znajduje się w pliku grader.cpp. Aby przetestować swój program, umieść pliki grader.cpp, meetings.cpp i meetings.h w tym samym katalogu i wykonaj następujące polecenie, aby skompilować programy.

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

Po pomyślnej kompilacji powstanie plik wykonywalny grader.

Zauważ, że właściwy program oceniający różni się od przykładowego. Przykładowy program oceniający będzie uruchamiany jako pojedynczy proces, który odczytuje dane ze standardowego wejścia i wypisuje wyniki na standardowe wyjście.

Wejście dla przykładowego programu oceniającego

Przykładowy program oceniający odczytuje ze standardowego wejścia następujące dane.

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

$A_i$ i $B_i$ ($0\le i\le N-2$) oznaczają, że wyspy $A_i$ i $B_i$ są bezpośrednio połączone mostem.

Wyjście dla przykładowego programu oceniającego

Gdy program zakończy się pomyślnie, przykładowy program oceniający wypisuje na standardowe wyjście poniższe informacje (cudzysłowy służą jedynie wyróżnieniu tekstu).

• Jeżeli Twój program zostanie uznany za poprawny, wypisuje liczbę wywołań funkcji Query, na przykład „Accepted: 100”.
• Jeżeli Twój program otrzyma wynik błędnej odpowiedzi, wypisuje jej rodzaj, na przykład „Wrong Answer [1]”.

Jeżeli Twój program otrzyma kilka rodzajów błędnej odpowiedzi, przykładowy program oceniający zgłosi tylko jeden z nich.

Ograniczenia

Definicje $A_i$ i $B_i$ znajdują się w sekcji „Wejście dla przykładowego programu oceniającego”.

• $3\le N\le 2\,000$.
• $0\le A_i<B_i\le N-1$ ($0\le i\le N-2$).
• Między dowolnymi wyspami można przemieszczać się, korzystając z mostów.
• Z każdą wyspą połączonych jest bezpośrednio co najwyżej $18$ mostów.

Podzadania

1. (7 punktów) $N\le 7$.
2. (10 punktów) $N\le 50$.
3. (12 punktów) $N\le 300$.

4. (71 punktów) Brak dodatkowych ograniczeń.

5. W podzadaniach 1, 2 i 3, jeżeli Twój program jest poprawny dla wszystkich przypadków testowych danego podzadania, otrzymujesz pełną liczbę punktów.

6. W podzadaniu 4, jeżeli Twój program jest poprawny dla wszystkich przypadków testowych, liczba punktów jest następująca, gdzie $X$ oznacza największą liczbę wywołań funkcji Query w jednym przypadku testowym.

   • 49 punktów, jeżeli $40\,000<X\le 100\,000$, oraz
   • 71 punktów, jeżeli $X\le 40\,000$.

Przykład

Poniżej przedstawiono przykładowe wejście dla przykładowego programu oceniającego oraz odpowiadające mu wywołania funkcji.

Wejście 1

5
0 1
0 2
1 3
1 4

Przykładowe wywołania