该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

云小安的系统

此题仅允许使用 C++ 语言提交。

题目背景

跨年夜的灯会布线是一棵树。云小安设计的系统里藏着两盏故障灯 $s\neq t$，它们会在 $0$ 点前熄灭。你看不到它们的编号，但你有一台“回声指引器”。

你对任意节点 $x$ 发起一次探测，指引器会分别给出“从 $x$ 出发，朝着 $s$ 走的第一步”和“从 $x$ 出发，朝着 $t$ 走的第一步”。但为了防止你区分哪一步对应哪盏灯，指引器会把这两步排序后返回。

你需要在有限探测次数内找出 $s,t$。

题目描述

本题为函数交互题。

存在一棵无向树 $T$，节点编号为 $1\dots n$，$T$ 连通且无环。

存在两个互不相同的隐藏节点 $s\neq t$。

对任意节点 $x$ 与目标 $y\in\{s,t\}$，定义：

• 若 $x=y$，则 $\mathrm{step}(x,y)=x$；
• 否则 $\mathrm{step}(x,y)$ 为 $x$ 的一个邻点，且位于从 $x$ 到 $y$ 的唯一路径上（即从 $x$ 朝 $y$ 走的第一步）。

一次询问 query(x) 会返回两个整数 $a\le b$，满足：

$$\{a,b\}=\{\mathrm{step}(x,s),\ \mathrm{step}(x,t)\}. $$

注意返回的是排序后的结果，因此你无法知道哪一个对应 $s$、哪一个对应 $t$。

你的任务是在询问次数限制内，输出这两个隐藏节点 $s,t$（顺序任意）。

交互库与接口说明

你可以调用 light.h 进行交互，交互命令有以下四种。

int getn()

返回整数 $n$，满足：

• $2 \le n \le 2\cdot 10^5$。

你应当在程序一开始调用此函数，并且仅调用一次。

void geted(int i, int &u, int &v)

获取树的第 $i$ 条边（$1\le i\le n-1$），返回该边两端点 $u,v$。

• 保证 $1\le u,v\le n$ 且 $u\neq v$。

void query(int x, int &a, int &b)

询问节点 $x$（要求 $1\le x\le n$），返回两个整数 $a,b$（按从小到大排序，即保证 $a\le b$），满足：

$$\{a,b\}=\{\mathrm{step}(x,s),\ \mathrm{step}(x,t)\}. $$

你最多可以调用 query $Q$ 次，其中：

$$Q = 3\cdot \left\lceil \log_2 n \right\rceil + 20. $$

超过次数将被判定为错误（RE/WA）。

void submit(int s, int t)

当你确定故障灯位置后，调用此函数提交答案。

要求：

• $1\le s,t\le n$；
• $s\neq t$。

允许输出顺序任意：submit(s,t) 与 submit(t,s) 等价。

提交后你不应当再进行任何交互操作。

数据范围

对于 $15\%$ 的数据，满足 $n\le 2000$。

对于另 $25\%$ 的数据，满足 $n\le 5\times 10^4$。

对于 $100\%$ 的数据，满足 $n\le 2\times 10^5$。

对所有测试点：询问次数上限均为 $Q=3\lceil\log_2 n\rceil+20$。

交互库请从 附件 下载，不保证其实现一定与评测时采用的交互库相同。