Tato úloha je interaktivní.

Během tohoto svátku plného sladké vůně narazila příprava závěrečného dezertu — mléčného dezertu se dvěma škraloupy — na poslední překážku.

Jako nejoblíbenější dezert v podniku musí dokonalý mléčný dezert se dvěma škraloupy dokonale spojit horní vrstvu dortu se spodní vrstvou pudinku. V tomto kouzelném bleším království se energie obou dezertních vrstev vzájemně prolínají a skrývají se ve složité síti měst.

Dva zkušení mistři dezertů v podniku — dacake8 a dapudding8 — se rozhodli vás vyzkoušet. Dort a pudink ukryli na silnicích mezi městy. Tento závěrečný mléčný dezert se dvěma škraloupy můžete úspěšně dokončit pouze tak, že se jich budete dotazovat a přesně určíte město, které je spojeno s hlavní provozovnou, v níž se nacházíte (město $1$), silnicí s ukrytým dezertem!

Existuje $n$ měst a každá dvojice měst je spojena silnicí. Existuje $n-1$ kusů dortu; $i$-tý kus se nachází na silnici spojující města $u_{i,1}$ a $v_{i,1}$. Existuje $n-1$ kusů pudinku; $i$-tý kus se nachází na silnici spojující města $u_{i,2}$ a $v_{i,2}$. Silnice s dortem tvoří jeden strom a silnice s pudinkem tvoří druhý strom.

Zpočátku neznáte konkrétní umístění dortů ani pudinků. dacake8 a dapudding8 můžete položit nejvýše $\min(1000,\frac{n\times(n-1)}{2})$ dotazů:

• Dotážete se dacake8 a dapudding8 na města $u$ a $v$. Multimnožina $S$ je na začátku prázdná.

  • dacake8 vyjde z města $u$, po cestě tvořené silnicemi s dortem dojde do města $v$ a do multimnožiny $S$ přidá čísla měst, kterými prošel.
  • dapudding8 vyjde z města $u$, po cestě tvořené silnicemi s pudinkem dojde do města $v$ a do multimnožiny $S$ přidá čísla měst, kterými prošel.
• Interaktivní knihovna vrátí multimnožinu $S$.

Nacházíte se ve městě $1$. Po dokončení dotazů musíte uvést město $u$ takové, že na silnici spojující města $1$ a $u$ se nachází některý druh dezertu.

dacake8 a dapudding8 vám nechtějí dělat potíže a zaručují, že umístění dortů i pudinků je určeno před položením dotazů. Jinými slovy, interaktivní knihovna není adaptivní.

Podrobnosti implementace

Soutěžící nemusí a ani nemají implementovat funkci main.

Ve zdrojovém souboru milk.cpp musíte zahrnout hlavičkový soubor milk.h a implementovat následující dvě funkce:

void init(int c, int t);

• $c,t$ označují číslo podúlohy a počet testovacích případů. $id=0$ znamená, že daný test je ukázkový.
• Pro každý test interaktivní knihovna zavolá tuto funkci právě jednou při zahájení běhu programu.

int find(int c, int n);

• $c,n$ označují číslo podúlohy a počet měst.
• Tato funkce musí vrátit kladné celé číslo $u$, které určuje město $u$ takové, že na silnici spojující města $1$ a $u$ se nachází některý druh dezertu.
• Pro každý test interaktivní knihovna zavolá tuto funkci právě $t$-krát.

Jeden dotaz můžete položit zavoláním následující funkce:

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

• $u,v$ určují dvě města $u$ a $v$.
• Musíte zajistit, že $1\le u,v\le n$ a $u\ne v$.
• Tato funkce vrátí multimnožinu $S$, jejíž přesný význam je uveden v popisu úlohy.
• Je-li velikost multimnožiny $S$ rovna $m$, platí $1\le S_i\le n$ a $S_0\le S_1\le \ldots \le S_{m-1}$.
• Musíte zajistit, aby během každého volání funkce find interaktivní knihovnou počet volání této funkce nepřesáhl $1000$.

Testování programu

Umístěte milk.cpp, milk.h a soubor grader.cpp z přílohy do stejného adresáře a zkompilujte je pomocí C++17:

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

Pro vzniklý spustitelný soubor milk platí následující:

První řádek vstupu interaktivní knihovny obsahuje dvě nezáporná celá čísla $id,t$, která označují číslo testu a počet testovacích případů.

Pro každý testovací případ obsahuje první řádek kladné celé číslo $n$, které udává počet měst. Každý z řádků $2\sim n$ obsahuje dvě kladná celá čísla $u_{i,1}$, $v_{i,1}$; každý z následujících $n-1$ řádků obsahuje dvě kladná celá čísla $u_{i,2}$, $v_{i,2}$.

Pokud jsou odpovědi všech $t$ volání funkce find správné, interaktivní knihovna vypíše na prvním řádku Correct! a na druhém řádku Max queries used: Q, kde $Q$ označuje největší počet volání funkce query ze všech testovacích případů. Pokud je alespoň jedna odpověď nesprávná, vypíše Wrong answer.; pokud je některé volání rozhraní neplatné, vypíše navíc na standardní chybový výstup důvod chyby.

Příklady

Vstup 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

Výstup 1

Correct!
Max queries used: 28

Poznámka

Upozorňujeme, že závěrečná testovací data neobsahují ukázkové případy.

Červené hrany na obrázcích znamenají, že se na silnici mezi dvěma městy nachází kus dortu; modré hrany znamenají, že se na silnici mezi dvěma městy nachází kus pudinku.

Pro první testovací případ vypadají stromy tvořené silnicemi s dortem a pudinkem následovně:

Pro druhý testovací případ vypadají stromy tvořené silnicemi s dortem a pudinkem následovně:

Ve třetím testovacím případě může být na jedné silnici současně dort i pudink.

Omezení

Zvláštní vlastnost $\text{A}$: Umístění dortů i pudinků je generováno zcela náhodně.

Zvláštní vlastnost $\text{B}$: Je zaručeno, že existuje právě jedna možná odpověď.

Zvláštní vlastnost $\text{C}$: Pokud oba stromy tvořené silnicemi s dortem a pudinkem zakořeníme ve městě $1$ a z každého města vedeme v každém ze dvou stromů orientovanou hranu do jeho rodičovského města, tvoří výsledný orientovaný graf DAG.

Zvláštní vlastnost $\text{D}$: Pokud oba stromy tvořené silnicemi s dortem a pudinkem zakořeníme ve městě $2$ a z každého města vedeme v každém ze dvou stromů orientovanou hranu do jeho rodičovského města, tvoří výsledný orientovaný graf DAG.

Zvláštní vlastnost $\text{E}$: Umístění pudinků je generováno zcela náhodně. Umístění dortů nezávisí na umístění pudinků.

Zvláštní vlastnost $\text{F}$: Oba stromy tvořené silnicemi s dortem a pudinkem jsou řetězce a oba začínají ve městě $1$.

V této úloze se náhodné generování stromu definuje pomocí náhodné Prüferovy posloupnosti.

Bodování

Pokud je odpověď vrácená funkcí find nesprávná nebo jsou parametry funkce query neplatné, je násobitel skóre daného testu roven $0$.

Pro podúlohy $1,2,3$ je násobitel skóre daného testu roven $0$, pokud počet dotazů překročí $\frac{n\times(n-1)}{2}$; jinak je roven $1$.

Pro podúlohy $4\sim 15$ označme $Q$ největší počet volání funkce query ze všech testovacích případů. Násobitel skóre $f(Q)$ se vypočítá podle následující tabulky:

Konečné skóre testu se rovná bodové hodnotě testu vynásobené násobitelem skóre a podle pravidel UOJ pro reálná skóre se uvádí na tři desetinná místa.

Časový limit: $20\ \mathrm{s}$.

Paměťový limit: $512\ \mathrm{MiB}$.