问题描述

高桥君一心想要求出树的直径。树是一种由顶点和连接它们的边组成的结构"图"的一种，当顶点的数量为$N$时，边的数量为$N-1$，每个顶点都通过边与其他所有顶点直接或间接地连接。

在这个问题中，边上带有整数权重。将两个顶点之间的距离定义为连接这两个顶点的边的权重的和。

树的直径是两个最远的顶点之间的距离。

让我们考虑以下这样的树。边旁边写的数字是边的权重。

在这种情况下，顶点1和2之间的距离为1，顶点2和4之间的距离为1+2=3。顶点3和5之间的距离为3+4=7，顶点4和5之间的距离也为2+1+4=7，这个距离在该树的顶点之间是最长的，所以树的直径为7。

高桥君对从顶点数量和两个顶点之间的距离信息中求出树的直径产生了兴趣。在这个问题中，您将首先给出树的顶点数$N$，然后进行几次询问，询问两个顶点之间的距离，最后求出树的直径。

但是，查询次数有限制。

请编写一个程序，在限制的查询次数内求出树的直径。

---

输入输出

首先，给出树的顶点数$N$。

$N$

接下来，您的程序将向响应程序发出一些问题。问题的格式如下：

? $a$ $b$

通过此问题，$a$和$b$之间的距离将在一行输入中传递。必须满足$1≤a, b≤N$且$a≠b$。

在进行了若干次问题之后，您将猜测出树的直径。设树的直径为$diameter$，

! $diameter$

用以下格式输出。在输出了树的直径之后，您的程序必须立即结束。如果没有结束，评判结果是不确定的。

此外，对于以这些格式之外的方式输出的评判结果也是不确定的。

在此问题中，每个测试用例都设置了查询次数的上限值，如果程序的查询次数超过该上限值，则判断为错误答案。

是否为正确答案取决于树的直径的输出。即使只询问了不能确定直径的问题，只要直径正确，也算作正确答案。

---

以几种语言为例，介绍了通过问题和回答的方式来获得顶点1和顶点2之间的距离。

但是，除了这里写的方法以外，也可以进行输入输出。

注意，在输出后必须刷新输出。如果没有刷新，可能会导致TLE。

C

printf("? %d %d\\n", 1, 2);
fflush(stdout);
scanf("%d", &dist);

C++

cout << "? " << 1 << " " << 2 << endl;
cin >> dist;

Java

System.out.printf("? %d %d\\n", 1, 2);
Scanner scanner = new Scanner(System.in);
dist = scanner.nextInt();

C#

Console.WriteLine("? {0} {1}", 1, 2);
dist = int.Parse(Console.ReadLine());

D

writeln("? ", 1, " ", 2);
stdout.flush();
dist = readln.chomp.to!int;

PHP

echo "? ", 1, " ", 2, PHP_EOL;
$dist = trim(fgets(STDIN));

Python

print "? {0} {1}".format(1, 2)
sys.stdout.flush()
dist = int(raw_input())

Perl

$|=1;
print "? ", 1, " ", 2, "\\n";
$dist = <>;

Ruby

print "? ", 1, " ", 2, "\\n"
STDOUT.flush
dist = gets.to_i

约束条件

• $2≤N≤50$
• $1≤(每条边的权重)≤10^6$

---

部分分

这个问题有部分分。

• 在20分的测试用例中，查询次数上限是1300次。
• 在另外80分的测试用例中，查询次数上限是100次。

输入输出示例

当树具有以下形状时，

可以考虑以下输入输出。

输入到程序

程序的输出

5

? 1 2

5

? 2 4

1

? 4 5

2

? 2 3

9

? 1 5

8

! 14

这是一个示例输入输出，不一定是进行了有意义的问题。