背景

我常常追忆过去。

虽然，过去的棱角曾深深创伤了我……

当我顺着时间的长河而上时，我看到那些令我窒息的过往，重新定格在脑海，化作天上的朵朵白云。

我看到一棵树，随着时间的流逝伸展枝桠，在变化的点权中追寻着一棵树的价值……

我看到一家店，里面的人在思考，思考在清仓甩卖糖果时收益最大的标价方案……

我看到一个人，正自顾自地玩着谐音替换的游戏，即使不小心加多或减少了几个字符也乐此不疲……

我看到一座城，这里刚刚被灾害侵袭，正在进行紧张的道路修复工作……

我看到一段过往，纵使曾经令我彻夜难眠，但心中的创伤被时间抚平后，终于能看清它们在岁月的长河里熠熠生辉……

最后，当我走到时间的起点，追忆之旅的尽头，我看到了我，那个从联合省选 2025 考场上走出来的我。

我看到了他脸上的无奈……

我听到他对我说……

或者，我希望有一天，他能笑着对我说……

“我常常追忆过去。”

题目描述

这是一道交互题。

这是这个问题的困难版本。两个版本的不同之处在于，本题中你有 $n$ 次“追忆”的机会。

有一张 $n$ 个点 $m$ 条边的无向连通图（边权均为 $1$），不幸的是，你忘记了 $1$ 到 $n$ 之间的最短路。

你有 $n$ 次“追忆”的机会，每次“追忆”，你可以想起两个点之间的最短路长度。

由于你实在想不起 $1$ 到 $n$ 的最短路长度了，你需要在不直接“追忆” $1$ 到 $n$ 之间的最短路的情况下，求出 $1$ 到 $n$ 的最短路。

但是，追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。为了满足你对美的苛求，在本题中，你的输出与标准答案的差的绝对值不超过 $1$ 即视为通过。

交互格式

首先你可以读入一个正整数 $n$，表示点的个数，注意：你无法读入也不需要读入边数 $m$！

当你想要“追忆”时，输出一行 ? x y 表示询问 $x$ 至 $y$ 的最短路长度，你需要保证 $1 \le x \le y \le n$ 且 $(x,y) \not= (1,n)$。若你的询问不符合上述要求或询问次数超过 $n$，交互库会返回 WA，否则交互库会输出一个正整数表示最短路长度。

当你确定了答案时，可以输出一行 ! x 表示你求出的答案，若你的答案与标准答案相差不超过 $1$，交互库会返回 AC，否则交互库会返回 WA。

输入格式

见上文的交互格式。

输出格式

见上文的交互格式。

3

1

2

? 1 2

? 2 3

! 1

5

1

1

1

1

? 1 2

? 2 3

? 3 4

? 4 5

! 4

提示

注意：样例仅作为交互格式展示，不一定具有逻辑。

【数据范围】

本题采用 Subtask 捆绑测试：

对于 $100\%$ 的数据，保证 $2 \le n \le 500$，给定的图是一张连通图。