题目描述

有一棵包含 $N$ 个顶点的树，每个顶点编号为 $1,\ldots,N$。
对于每一对整数 $u,v\,\ (1\leq u,v\leq N)$，定义顶点 $u$ 和顶点 $v$ 之间的距离 $d_{u,v}$ 为：

• 在连接顶点 $u$ 和顶点 $v$ 的最短路径上包含的边的数量。

你可以进行 $0$ 次以上、$2N$ 次以下的如下询问：

• 指定满足 $1\leq u,v\leq N$ 且 $u+v>3$ 的整数 $u,v$，询问顶点 $u$ 和顶点 $v$ 的距离 $d_{u,v}$。

请你求出顶点 $1$ 和顶点 $2$ 之间的距离 $d_{1,2}$。

输入格式

本题为交互题（你的程序需要与评测程序通过输入输出进行交互）。

首先，你的程序会从标准输入读入一个正整数 $N$。

$N$

之后，你可以进行询问。
每次询问请按如下格式输出到标准输出（末尾需换行）：

? $u$ $v$

如果询问合法，你会从标准输入读入该询问的答案 $d_{u,v}$。

$d_{u,v}$

如果你的询问格式错误、询问次数超限等导致询问被判为不合法，你会收到 $-1$ 作为回应。

-1

此时，评测程序会立即终止，判定你的提交为不正确。你的程序也应立即终止。

当你确定 $d_{1,2}$ 的值后，请按如下格式输出答案（末尾需换行）：

! $d_{1,2}$

输出格式

见上文交互格式说明。

说明/提示

限制

• $3\leq N\leq 100$
• $N$ 是整数
• 树在交互开始前已确定

注意事项

• 每次输出后请务必刷新标准输出，否则可能会因超时（TLE）被判为不正确。
• 输出答案后（或收到 $-1$ 后）请立即正常退出程序，否则评测结果不确定。
• 输出格式不正确时，评测结果不确定。
• 特别注意，不要输出多余的换行，否则会被判为格式错误。

输入输出样例

以下为当树结构如图所示时的交互样例：

输入 输出 说明
3 首先给出整数 $N$。
? 1 3 第一次询问，询问顶点 $1,3$ 的距离。
1 返回顶点 $1,3$ 的距离。
? 2 2 第二次询问，询问顶点 $2,2$ 的距离。
0 返回顶点 $2,2$ 的距离。
? 2 3 第三次询问，询问顶点 $2,3$ 的距离。
1 返回顶点 $2,3$ 的距离。
? 3 1 第四次询问，询问顶点 $3,1$ 的距离。
1 返回顶点 $3,1$ 的距离。
? 3 2 第五次询问，询问顶点 $3,2$ 的距离。
1 返回顶点 $3,2$ 的距离。
? 2 2 第六次询问，询问顶点 $2,2$ 的距离。
0 返回顶点 $2,2$ 的距离。
! 2 输出顶点 $1,2$ 的距离并结束。实际树中顶点 $1,2$ 的距离为 $2$，因此本次提交可以通过。

由 ChatGPT 4.1 翻译