本题为交互题。

在这个充满甜香的节日里，压轴甜品——双皮奶的制作遇到了一道最后的难关。

作为店里最受欢迎的甜品，一份完美的双皮奶需要将上层的蛋糕与下层的布丁完美融合。在这个神奇的跳蚤王国中，两层甜品元素的能量相互交织，隐藏在复杂的城市网络之中。

店里两位资深的甜品大师——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$。询问结束后，你需要给出一个城市 $u$，满足连接城市 $1$ 和城市 $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$ 分别表示子任务编号与城市的数量。
• 该函数需要返回一个正整数 $u$，表示给出一个城市 $u$，满足连接城市 $1$ 和城市 $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}$。

若 $t$ 次调用 find 答案均正确，交互库输出第一行 Correct!，第二行 Max queries used: Q，其中 $Q$ 表示所有测试数据中调用 query 次数的最大值。若至少有一次答案错误，则输出 Wrong answer.；若接口调用不合法，还会在标准错误流给出错误原因。

样例

input

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

output

Correct!
Max queries used: 28

explanation

请注意，最终测试数据中不含有样例。

图中红色边表示两个城市间的道路上有一块蛋糕，蓝色边表示两个城市间的道路上有一块布丁。

对于第一组数据，蛋糕、布丁的道路构成的树的形态如下：

对于第二组数据，蛋糕、布丁的道路构成的树的形态如下：

对于第三组数据，一条道路上也可以同时有蛋糕和布丁。

数据范围

特殊性质 $\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}$。