Det här är en interaktiv uppgift.

Under denna högtid, fylld av söta dofter, har tillagningen av den avslutande desserten — mjölkpudding med dubbelt skinn — stött på ett sista hinder.

Som butikens populäraste dessert kräver en perfekt mjölkpudding med dubbelt skinn att det övre lagret av kaka och det undre lagret av pudding förenas perfekt. I detta magiska lopprike flätas energin från de två dessertlagrens beståndsdelar samman och döljs i ett komplicerat nätverk av städer.

Butikens två erfarna dessertmästare — dacake8 och dapudding8 — har bestämt sig för att pröva dig. De har gömt kaka respektive pudding på vägarna mellan städerna. Bara genom att fråga dem och exakt hitta en stad som är förbunden med huvudbutiken där du befinner dig (stad $1$) genom en väg där en dessert finns gömd kan du färdigställa denna avslutande mjölkpudding med dubbelt skinn!

Det finns $n$ städer, med en väg mellan varje par av städer. Det finns $n-1$ kakbitar; den $i$:te ligger på vägen mellan städerna $u_{i,1}$ och $v_{i,1}$. Det finns $n-1$ puddingbitar; den $i$:te ligger på vägen mellan städerna $u_{i,2}$ och $v_{i,2}$. Vägarna med kaka respektive pudding bildar två träd.

Till en början känner du inte till kakans och puddingens exakta placeringar. Du får ställa högst $\min(1000,\frac{n\times(n-1)}{2})$ frågor till dacake8 och dapudding8:

• Du frågar dacake8 och dapudding8 om städerna $u$ och $v$. Multimängden $S$ är från början tom.
  • dacake8 utgår från stad $u$, följer stigen med kaka till stad $v$ och lägger till numren på de passerade städerna i multimängden $S$.
  • dapudding8 utgår från stad $u$, följer stigen med pudding till stad $v$ och lägger till numren på de passerade städerna i multimängden $S$.
• Interaktionsbiblioteket returnerar multimängden $S$.

Du befinner dig i stad $1$. När frågorna är slut ska du ange en stad $u$ sådan att vägen mellan stad $1$ och stad $u$ innehåller någon sorts dessert.

dacake8 och dapudding8 vill inte göra det svårt för dig. De garanterar att kakans och puddingens placeringar bestäms innan frågorna ställs. Med andra ord är interaktionsbiblioteket icke-adaptivt.

Implementationsdetaljer

Du behöver inte, och ska inte, implementera funktionen main.

Du ska inkludera headerfilen milk.h i källfilen milk.cpp och implementera följande två funktioner:

void init(int c, int t);

• $c,t$ anger deluppgiftens nummer respektive antalet testfall. $id=0$ betyder att testgruppen är ett exempel.
• För varje testgrupp anropas denna funktion av interaktionsbiblioteket exakt en gång när programmet börjar köras.

int find(int c, int n);

• $c,n$ anger deluppgiftens nummer respektive antalet städer.
• Funktionen ska returnera ett positivt heltal $u$ som anger en stad $u$ sådan att vägen mellan stad $1$ och stad $u$ innehåller någon sorts dessert.
• För varje testgrupp anropas denna funktion av interaktionsbiblioteket exakt $t$ gånger.

Du kan ställa en fråga genom att anropa följande funktion:

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

• $u,v$ anger de två städerna $u$ och $v$.
• Du måste säkerställa att $1\le u,v\le n$ och $u\ne v$.
• Funktionen returnerar multimängden $S$, vars betydelse beskrivs i uppgiftstexten.
• Om multimängden $S$ har storlek $m$ gäller $1\le S_i\le n$ och $S_0\le S_1\le \ldots \le S_{m-1}$.
• Varje gång interaktionsbiblioteket anropar find måste du säkerställa att denna funktion anropas högst $1000$ gånger.

Testning av programmet

Placera milk.cpp, milk.h och den bifogade filen grader.cpp i samma katalog och kompilera med C++17:

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

För den kompilerade körbara filen milk gäller följande:

Den första raden i interaktionsbibliotekets indata innehåller två icke-negativa heltal $id,t$, som anger testgruppens nummer respektive antalet testfall.

För varje testfall innehåller den första raden ett positivt heltal $n$, som anger antalet städer. Raderna $2\sim n$ innehåller vardera två positiva heltal $u_{i,1}$, $v_{i,1}$; de följande $n-1$ raderna innehåller vardera ytterligare två positiva heltal $u_{i,2}$, $v_{i,2}$.

Om svaren från alla $t$ anrop till find är korrekta skriver interaktionsbiblioteket ut Correct! på den första raden och Max queries used: Q på den andra, där $Q$ är det största antalet anrop till query bland alla testfall. Om minst ett svar är fel skrivs Wrong answer. ut; om ett anrop till gränssnittet är ogiltigt anges också orsaken i standardfelströmmen.

Exempel

Indata 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

Utdata 1

Correct!
Max queries used: 28

Förklaring

Observera att exemplen inte ingår i de slutliga testdata.

I figurerna betyder en röd kant att det finns en kakbit på vägen mellan de två städerna, och en blå kant betyder att det finns en puddingbit på vägen mellan de två städerna.

För det första testfallet har träden som bildas av vägarna med kaka respektive pudding följande utseende:

För det andra testfallet har träden som bildas av vägarna med kaka respektive pudding följande utseende:

För det tredje testfallet kan en väg innehålla både kaka och pudding samtidigt.

Begränsningar

Särskild egenskap $\text{A}$: Kakans och puddingens placeringar genereras helt slumpmässigt.

Särskild egenskap $\text{B}$: Det garanteras att det bara finns ett möjligt svar.

Särskild egenskap $\text{C}$: Om båda träden som bildas av vägarna med kaka respektive pudding rotas i stad $1$, och varje stad förbinds med riktade kanter till sin föräldrastad i vart och ett av de två träden, bildar den resulterande riktade grafen en DAG.

Särskild egenskap $\text{D}$: Om båda träden som bildas av vägarna med kaka respektive pudding rotas i stad $2$, och varje stad förbinds med riktade kanter till sin föräldrastad i vart och ett av de två träden, bildar den resulterande riktade grafen en DAG.

Särskild egenskap $\text{E}$: Puddingens placeringar genereras helt slumpmässigt. Kakans placeringar beror inte på puddingens placeringar.

Särskild egenskap $\text{F}$: De två träden som bildas av vägarna med kaka respektive pudding är två kedjor, och båda börjar i stad $1$.

I denna uppgift definieras slumpmässig generering av ett träd som användning av en slumpmässig Prufer-sekvens.

Poängsättning

Om svaret som returneras av find är felaktigt eller parametrarna till query är ogiltiga blir testgruppens poängfaktor $0$.

För deluppgifterna $1,2,3$ gäller att om antalet frågor överstiger $\frac{n\times(n-1)}{2}$ blir testgruppens poängfaktor $0$; annars blir poängfaktorn $1$.

För deluppgifterna $4\sim 15$, låt $Q$ vara det största antalet anrop till query bland alla testfall. Poängfaktorn $f(Q)$ beräknas enligt följande tabell:

Testgruppens slutliga poäng är dess poängvärde multiplicerat med poängfaktorn, avrundat till tre decimaler enligt UOJ:s regler för reella poäng.

Tidsgräns: $20\ \mathrm{s}$.

Minnesgräns: $512\ \mathrm{MiB}$.