题目描述

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

• 顶点 $u$ 和 $v$ 之间最短路径上所包含的边的数量。

你可以在以下形式的问题中询问 $0$ 到 $2N$ 个问题（包括两端）。

• 询问顶点 $u,v$ 之间的距离 $d_{u,v}$，其中 $1\leq u,v \leq N$ 且 $u+v>3$。

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

约束条件

• $3 \leq N \leq 100$
• $N$ 是整数。
• 在程序和评测系统进行交互之前，树已经被确定。

输入和输出

这是一个交互式任务，你的程序通过输入和输出与评测系统进行交互。

首先，从标准输入中读入一个正整数 $N$：

$N$

然后，你可以提出问题。
一个问题应该以以下格式打印出来（末尾带有换行符）：

? $u$ $v$

如果问题是有效的，从标准输入中给出响应 $d_{u,v}$：

$d_{u,v}$

如果问题被判定为无效，例如格式有误或者你提问次数过多，你将得到响应 -1 替代：

-1

此时，你的提交已被判定为错误。评测系统的程序随后终止；你的程序也应该尽快终止。

当你找到答案 $d_{1,2}$ 时，请以以下格式打印到标准输出（末尾带有换行符）：

! $d_{1,2}$

注意事项

• 在每次输出后使用 Flush Standard Output。否则，可能导致超时错误。