高桥君正沉迷于求树的直径。树是一种由顶点和连接这些顶点的边组成的结构（“图”中的一种），如果顶点数为 $N$，则边的数量为 $N-1$，并且任意两个顶点都通过边直接或间接连通。

在本题中，每条边都有一个整数权重。定义两个顶点之间的距离为连接这两个顶点的路径上所有边权的和。

树的直径指的是所有顶点对中距离最大的那一对顶点之间的距离。

比如，考虑如下的树。边上的数字表示该边的权重。

在这个例子中，顶点 $1$ 和 $2$ 之间的距离为 $1$，顶点 $2$ 和 $4$ 之间的距离为 $1+2=3$。顶点 $3$ 和 $5$ 之间的距离为 $3+4=7$，顶点 $4$ 和 $5$ 之间的距离也是 $2+1+4=7$。这个树中最大的距离是 $7$，因此树的直径为 $7$。

高桥君对通过顶点数和两点间距离信息来求树的直径产生了兴趣。本题中，你将首先获得树的顶点数 $N$，然后可以多次询问任意两点之间的距离，最终要求你求出树的直径。

不过，询问两点间距离的次数有限制。

请在限定的询问次数内，编写程序求出树的直径。

首先，树的顶点数 $N$ 通过标准输入给出。

$N$

接下来，你的程序可以多次向评测程序发起询问。询问的格式如下：

? $a$ $b$

通过这个询问，你可以获得 $a$ 和 $b$ 之间的距离，评测程序会将结果通过标准输入返回一行。要求 $1 \leq a, b \leq N$ 且 $a \neq b$。

在进行若干次询问后，你需要输出树的直径。假设树的直径为 $diameter$，则输出格式如下：

! $diameter$

输出树的直径后，程序必须立即结束。如果没有立即结束，评测结果将不确定。

如果输出格式不符合上述要求，评测结果也将不确定。

本题每个测试点都有限定的最大询问次数。如果你的询问次数超过上限，将被判为错误。

判定正误以你输出的树的直径为准。即使你的询问不能唯一确定直径，只要输出的直径是正确的，也会被判为正确。

---

以下是一些语言中，如何询问顶点 $1$ 和 $2$ 之间距离并读取结果 $dist$ 的示例。

注意，输出后需要刷新缓冲区（flush），否则可能会TLE。

C

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

C++

cout << "? " << 1 << " " << 2 << endl;
cout.flush();
cin >> dist;

Java

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

C#

Console.WriteLine("? {0} {1}", 1, 2);
Console.Out.Flush();
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 = <STDIN>;

Ruby

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

输入格式

无特殊输入格式说明，见题目描述。

无特殊输出格式说明，见题目描述。

限制

• $2 \leq N \leq 50$
• $1 \leq$（每条边的权重）$\leq 10^6$

部分分

本题设置了部分分。

• 有 $20$ 分的测试点，询问次数上限为 $1300$ 次。
• 另有 $80$ 分的测试点，询问次数上限为 $100$ 次。

输入输出样例

当树的结构如下图所示时：

可能的输入输出如下：

程序输入 程序输出 5 ? 1 2 5 ? 2 4 1 ? 4 5 2 ? 2 3 9 ? 1 5 8 ! 14

这只是输入输出的一个例子，未必是有意义的询问。

由 ChatGPT 4.1 翻译