分数: 500 点
问题陈述
有一棵树 N 顶点,编号 1, \ldots, N.
对于每对整数 u,v\, (1 \leq u,v \leq N),距离 d_{u,v} 顶点之间 u, v 定义如下。
- 连接顶点的最短路径中包含的边数 u 和 v.
您可以询问 0 和 2N 问题(含)采用以下形式。
- 询问距离 d_{u,v} 顶点之间 u,v 对于整数 u,v 您选择的 1\leq u,v \leq N 和 u+v>3.
求距离 d_{1,2} 顶点之间 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}
通知
- 每次输出后刷新标准输出。否则,您可能会得到 TLE 判决。
- 打印答案后(或收到
-1),立即正常终止程序。否则,判决将是不确定的。 - 对于格式错误的输出情况的判决是不确定的。
- 具体来说,请注意,过多的换行符也会被视为格式错误的输出。
示例输入和输出
以下是此图中所示树的示例交互。

| 输入 | 输出 | 说明 |
|---|---|---|
3 |
交互从整数开始 N. | |
? 1 3 |
作为 1-st问题,你问顶点之间的距离 1 和 3. | |
1 |
顶点之间的距离 返回 1,3 。 | |
? 2 2 |
作为 2-第一个问题,你问顶点之间的距离 2 和 2. | |
0 |
顶点之间的距离 返回 2,2 。 | |
? 2 3 |
作为 3-rd问题,你问顶点之间的距离 2 和 3. | |
1 |
顶点之间的距离 返回 2,3 。 | |
? 3 1 |
作为 4- 第题,你问顶点之间的距离 3 和 1. | |
1 |
顶点之间的距离 返回 3,1 。 | |
? 3 2 |
作为 5- 第题,你问顶点之间的距离 3 和 2. | |
1 |
顶点之间的距离 返回 3,2 。 | |
? 2 2 |
作为 6- 第题,你问顶点之间的距离 2 和 2. | |
0 |
顶点之间的距离 返回 2,2 。 | |
! 2 |
你猜测顶点之间的距离 1,2 并终止。他们之间的实际距离是 2,所以你会得到 AC 判决。 |