この問題はインタラクティブな問題です。

甘い香りに満ちたこのお祭りで、最後を飾るデザートである双皮奶（シュアンピーナイ）を作るために、最後の難関が待ち受けています。

店で最も人気のあるデザートである完璧な双皮奶には、上の層のケーキと下の層のプリンを見事に融合させる必要があります。この不思議なノミの王国では、二層のデザートの要素が持つエネルギーが互いに絡み合い、複雑な都市のネットワークの中に隠れています。

店の二人の熟練したデザート職人、dacake8 と dapudding8 は、あなたの腕を試すことにしました。二人はケーキとプリンをそれぞれ都市間の道路に隠しました。二人に尋ね、あなたがいる本店（都市 1）とつながっていてデザートが隠されている都市を正確に見つけてこそ、最後を飾るこの双皮奶を完成させることができます！

$n$ 個の都市があり、どの二つの都市の間にも道路があります。ケーキは $n-1$ 個あり、$i$ 番目のケーキは都市 $u_{i,1}$ と都市 $v_{i,1}$ を結ぶ道路上にあります。プリンも $n-1$ 個あり、$i$ 番目のプリンは都市 $u_{i,2}$ と都市 $v_{i,2}$ を結ぶ道路上にあります。ケーキがある道路とプリンがある道路は、それぞれ一つの木を構成します。

最初、あなたはケーキとプリンの具体的な位置を知りません。dacake8 と dapudding8 に、次の質問を最大 $\min(1000,\frac{n\times(n-1)}{2})$ 回行えます。

• dacake8 と dapudding8 に都市 $u$ と都市 $v$ について尋ねます。最初、多重集合 $S$ は空です。

  • dacake8 は都市 $u$ から出発し、ケーキがある道路からなる経路を通って都市 $v$ に到着し、通った都市の番号を多重集合 $S$ に追加します。
  • dapudding8 は都市 $u$ から出発し、プリンがある道路からなる経路を通って都市 $v$ に到着し、通った都市の番号を多重集合 $S$ に追加します。
• インタラクションライブラリは多重集合 $S$ を返します。

あなたがいるのは都市 $1$ です。質問を終えたら、都市 $1$ と都市 $u$ を結ぶ道路にいずれかの種類のデザートがあるような都市 $u$ を答える必要があります。

dacake8 と dapudding8 はあなたを困らせたいわけではないので、質問を始める前にケーキとプリンの位置が決められていることを保証します。つまり、インタラクションライブラリは非適応的です。

実装の詳細

main 関数を実装する必要はなく、実装してはいけません。

ソースファイル milk.cpp にヘッダーファイル milk.h をインクルードし、次の二つの関数を実装してください。

void init(int c, int t);

• $c,t$ は、それぞれ小課題の番号とテストケースの数を表します。$id=0$ は、そのテストが入出力例であることを表します。
• 各テストについて、この関数はプログラムの実行開始時にインタラクションライブラリからちょうど一度呼び出されます。

int find(int c, int n);

• $c,n$ は、それぞれ小課題の番号と都市の数を表します。
• この関数は、都市 $1$ と都市 $u$ を結ぶ道路にいずれかの種類のデザートがあるような都市 $u$ を表す正の整数 $u$ を返す必要があります。
• 各テストについて、この関数はインタラクションライブラリからちょうど $t$ 回呼び出されます。

次の関数を呼び出すことで、一度の質問を行えます。

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

• $u,v$ は、指定する二つの都市 $u$ と $v$ を表します。
• $1\le u,v\le n$ かつ $u\ne v$ を満たすようにしてください。
• この関数は多重集合 $S$ を返します。具体的な意味は問題文を参照してください。
• 多重集合 $S$ の大きさを $m$ とすると、$1\le S_i\le n$ かつ $S_0\le S_1\le \ldots \le S_{m-1}$ が成り立ちます。
• インタラクションライブラリによる find の各呼び出しに対して、この関数の呼び出し回数が $1000$ 回を超えないようにしてください。

プログラムのテスト方法

milk.cpp、milk.h、および添付ファイルの grader.cpp を同じディレクトリに置き、C++17 を使ってコンパイルしてください。

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

コンパイルして得られた実行ファイル milk について、次のようになります。

インタラクションライブラリへの入力の最初の行には、テストの番号とテストケースの数をそれぞれ表す二つの非負整数 $id,t$ が含まれます。

各テストケースの最初の行には、都市の数を表す正の整数 $n$ が与えられます。第 $2\sim n$ 行には、それぞれ二つの正の整数 $u_{i,1}$, $v_{i,1}$ が与えられます。その後の $n-1$ 行には、それぞれ二つの正の整数 $u_{i,2}$, $v_{i,2}$ が与えられます。

find の $t$ 回の呼び出しすべてで答えが正しい場合、インタラクションライブラリは最初の行に Correct!、二行目に Max queries used: Q を出力します。ここで、$Q$ はすべてのテストケースにおける query の呼び出し回数の最大値を表します。少なくとも一度答えが誤っていた場合は、Wrong answer. を出力します。インターフェースの呼び出しが不正な場合は、さらに標準エラー出力にその理由を出力します。

入出力例

入力 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

出力 1

Correct!
Max queries used: 28

注記

最終的なテストデータには、入出力例は含まれないことに注意してください。

図の赤い辺は二つの都市を結ぶ道路にケーキが一つあることを表し、青い辺は二つの都市を結ぶ道路にプリンが一つあることを表します。

最初のテストケースでは、ケーキがある道路とプリンがある道路からなる木の形は次のとおりです。

二番目のテストケースでは、ケーキがある道路とプリンがある道路からなる木の形は次のとおりです。

三番目のテストケースのように、一本の道路にケーキとプリンが同時に存在することもあります。

制約

特別な性質 $\text{A}$：ケーキとプリンの位置は完全にランダムに生成されます。

特別な性質 $\text{B}$：可能な答えが一意であることが保証されます。

特別な性質 $\text{C}$：ケーキがある道路とプリンがある道路からなる二つの木で、都市 $1$ を根とし、各都市からそれぞれの木における親の都市へ辺を張ったとき、得られる有向グラフは DAG になります。

特別な性質 $\text{D}$：ケーキがある道路とプリンがある道路からなる二つの木で、都市 $2$ を根とし、各都市からそれぞれの木における親の都市へ辺を張ったとき、得られる有向グラフは DAG になります。

特別な性質 $\text{E}$：プリンの位置は完全にランダムに生成されます。ケーキの位置はプリンの位置に依存しません。

特別な性質 $\text{F}$：ケーキがある道路とプリンがある道路からなる二つの木は二本の鎖であり、どちらも都市 $1$ が鎖の先頭です。

この問題で木をランダムに生成するとは、ランダムな Prufer 列を使って生成することを意味します。

小課題

find が返した答えが正しくない、または query の引数が不正な場合、そのテストの得点倍率は $0$ になります。

小課題 $1,2,3$ では、質問回数が $\frac{n\times(n-1)}{2}$ を超えた場合、そのテストの得点倍率は $0$ になり、そうでなければ得点倍率は $1$ になります。

小課題 $4\sim 15$ では、$Q$ をすべてのテストケースにおける query の呼び出し回数の最大値とします。得点倍率 $f(Q)$ は次の表に従って計算されます。

各テストの最終的な得点は、そのテストの配点に得点倍率を掛けた値であり、UOJ の実数得点の規則に従って小数点以下三桁まで保持されます。

時間制限：$20\ \mathrm{s}$。

メモリ制限：$512\ \mathrm{MiB}$。