To zadanie jest interaktywne.

Podczas tego święta przepełnionego słodkim aromatem przygotowanie deseru na wielki finał — mleka z podwójną skórką — napotkało ostatnią trudność.

Jako najpopularniejszy deser w lokalu idealne mleko z podwójną skórką wymaga doskonałego połączenia górnej warstwy ciasta z dolną warstwą budyniu. W tym magicznym królestwie pcheł energie obu warstw deseru splatają się ze sobą, ukryte w złożonej sieci miast.

Dwaj doświadczeni mistrzowie deserów z lokalu — dacake8 i dapudding8 — postanowili wystawić cię na próbę. Ukryli ciasto i budyń na drogach między miastami. Tylko zasięgając ich rady i dokładnie wskazując miasto połączone z głównym lokalem, w którym się znajdujesz (miastem 1), drogą skrywającą deser, możesz pomyślnie przygotować to finałowe mleko z podwójną skórką!

Istnieje $n$ miast, a każdą parę miast łączy droga. Jest $n-1$ kawałków ciasta; $i$-ty kawałek znajduje się na drodze łączącej miasta $u_{i,1}$ i $v_{i,1}$. Jest $n-1$ porcji budyniu; $i$-ta porcja znajduje się na drodze łączącej miasta $u_{i,2}$ i $v_{i,2}$. Drogi zawierające ciasto i drogi zawierające budyń tworzą odpowiednio dwa drzewa.

Początkowo nie znasz dokładnych położeń ciasta i budyniu. Możesz zadać dacake8 i dapudding8 co najwyżej $\min(1000,\frac{n\times(n-1)}{2})$ zapytań:

• Pytasz dacake8 i dapudding8 o miasta $u$ i $v$; początkowo multizbiór $S$ jest pusty.

  • dacake8 wyrusza z miasta $u$, dociera do miasta $v$ ścieżką złożoną z dróg zawierających ciasto i dodaje numery odwiedzonych miast do multizbioru $S$.
  • dapudding8 wyrusza z miasta $u$, dociera do miasta $v$ ścieżką złożoną z dróg zawierających budyń i dodaje numery odwiedzonych miast do multizbioru $S$.
• Biblioteka interaktywna zwraca multizbiór $S$.

Znajdujesz się w mieście $1$. Po zakończeniu zapytań musisz wskazać miasto $u$ takie, że na drodze łączącej miasta $1$ i $u$ znajduje się jakiś rodzaj deseru.

dacake8 i dapudding8 nie chcą ci utrudniać zadania i gwarantują, że położenia ciasta i budyniu zostały ustalone przed zadawaniem zapytań. Innymi słowy, biblioteka interaktywna jest nieadaptacyjna.

Szczegóły implementacji

Nie musisz i nie powinieneś implementować funkcji main.

W pliku źródłowym milk.cpp musisz dołączyć plik nagłówkowy milk.h i zaimplementować następujące dwie funkcje:

void init(int c, int t);

• $c,t$ oznaczają odpowiednio numer podzadania i liczbę zestawów danych testowych. $id=0$ oznacza, że dany test jest przykładem.
• Dla każdego testu biblioteka interaktywna wywoła tę funkcję dokładnie raz, przy rozpoczęciu działania programu.

int find(int c, int n);

• $c,n$ oznaczają odpowiednio numer podzadania i liczbę miast.
• Funkcja musi zwrócić dodatnią liczbę całkowitą $u$, wskazującą miasto $u$ takie, że na drodze łączącej miasta $1$ i $u$ znajduje się jakiś rodzaj deseru.
• Dla każdego testu biblioteka interaktywna wywoła tę funkcję dokładnie $t$ razy.

Możesz zadać jedno zapytanie, wywołując następującą funkcję:

std::vector<int>query(int u, int v);

• $u,v$ wskazują dwa miasta $u$ i $v$.
• Musisz zapewnić, że $1\le u,v\le n$ oraz $u\ne v$.
• Funkcja zwraca multizbiór $S$, którego znaczenie opisano w treści zadania.
• Jeśli rozmiar multizbioru $S$ wynosi $m$, to zachodzą $1\le S_i\le n$ oraz $S_0\le S_1\le \ldots \le S_{m-1}$.
• Musisz zapewnić, że podczas każdego wywołania find przez bibliotekę interaktywną liczba wywołań tej funkcji nie przekroczy $1000$.

Testowanie programu

Umieść milk.cpp, milk.h i załączony plik grader.cpp w tym samym katalogu i skompiluj je przy użyciu C++17:

g++ grader.cpp milk.cpp -o milk -O2 -std=c++17
./milk < ex_milk1.in

Dla otrzymanego pliku wykonywalnego milk:

Pierwszy wiersz wejścia biblioteki interaktywnej zawiera dwie nieujemne liczby całkowite $id,t$, oznaczające odpowiednio numer testu i liczbę zestawów danych testowych.

Dla każdego zestawu danych testowych pierwszy wiersz zawiera dodatnią liczbę całkowitą $n$, oznaczającą liczbę miast. Każdy z wierszy $2\sim n$ zawiera dwie dodatnie liczby całkowite $u_{i,1}$, $v_{i,1}$; każdy z następnych $n-1$ wierszy zawiera dwie dodatnie liczby całkowite $u_{i,2}$, $v_{i,2}$.

Jeśli odpowiedzi we wszystkich $t$ wywołaniach find są poprawne, biblioteka interaktywna wypisze w pierwszym wierszu Correct!, a w drugim Max queries used: Q, gdzie $Q$ oznacza największą liczbę wywołań query spośród wszystkich zestawów danych testowych. Jeśli choć jedna odpowiedź jest błędna, wypisze Wrong answer.; jeśli wywołanie interfejsu jest nieprawidłowe, dodatkowo poda przyczynę błędu na standardowym strumieniu błędów.

Przykład

Wejście 1

0 3
5
1 5
2 5
2 4
3 5
1 2
1 4
3 4
4 5
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 7
2 4
3 6
4 6
5 7
5 8
6 8
2
1 2
1 2

Wyjście 1

Correct!
Max queries used: 28

Uwagi

Uwaga: końcowe dane testowe nie zawierają przykładu.

Na rysunkach czerwona krawędź oznacza, że na drodze między dwoma miastami znajduje się kawałek ciasta, a niebieska krawędź oznacza, że znajduje się tam porcja budyniu.

Dla pierwszego zestawu danych drzewa utworzone przez drogi zawierające ciasto i budyń wyglądają następująco:

Dla drugiego zestawu danych drzewa utworzone przez drogi zawierające ciasto i budyń wyglądają następująco:

Dla trzeciego zestawu danych jedna droga może zawierać jednocześnie ciasto i budyń.

Ograniczenia

Szczególna własność $\text{A}$: położenia ciasta i budyniu są generowane całkowicie losowo.

Szczególna własność $\text{B}$: gwarantuje się, że istnieje dokładnie jedna możliwa odpowiedź.

Szczególna własność $\text{C}$: jeśli ukorzenimy oba drzewa utworzone przez drogi zawierające ciasto i budyń w mieście $1$ i z każdego miasta poprowadzimy krawędź skierowaną do jego rodzica w każdym z tych dwóch drzew, to otrzymany graf skierowany będzie DAG-iem.

Szczególna własność $\text{D}$: jeśli ukorzenimy oba drzewa utworzone przez drogi zawierające ciasto i budyń w mieście $2$ i z każdego miasta poprowadzimy krawędź skierowaną do jego rodzica w każdym z tych dwóch drzew, to otrzymany graf skierowany będzie DAG-iem.

Szczególna własność $\text{E}$: położenia budyniu są generowane całkowicie losowo. Położenia ciasta nie zależą od położeń budyniu.

Szczególna własność $\text{F}$: oba drzewa utworzone przez drogi zawierające ciasto i budyń są łańcuchami, a miasto $1$ jest początkiem każdego z nich.

W tym zadaniu losowe generowanie drzewa oznacza generowanie go za pomocą losowego ciągu Prufera.

Podzadania

Jeśli odpowiedź zwrócona przez find jest niepoprawna lub parametry query są nieprawidłowe, mnożnik punktacji dla danego testu wynosi $0$.

Dla podzadań $1,2,3$, jeśli liczba zapytań przekroczy $\frac{n\times(n-1)}{2}$, mnożnik punktacji dla danego testu wynosi $0$; w przeciwnym razie wynosi $1$.

Dla podzadań $4\sim 15$ niech $Q$ oznacza największą liczbę wywołań query spośród wszystkich zestawów danych testowych. Mnożnik punktacji $f(Q)$ jest obliczany według poniższej tabeli:

Końcowy wynik dla danego testu jest iloczynem liczby punktów przypisanej temu testowi i mnożnika punktacji, zaokrąglonym do trzech miejsc po przecinku zgodnie z zasadami punktacji rzeczywistej UOJ.

Limit czasu: $20\ \mathrm{s}$.

Limit pamięci: $512\ \mathrm{MiB}$.