P16824 [AFOI 2025] A2.追忆（Hard Version）

我常常追忆过去。 虽然，过去的棱角曾深深创伤了我…… 当我顺着时间的长河而上时，我看到那些令我窒息的过往，重新定格在脑海，化作天上的朵朵白云。 我看到一棵树，随着时间的流逝伸展枝桠，在变化的点权中追寻着一颗**树的价值**…… 我看到一家店，里面的人在思考，思考在**清仓甩卖**糖果时收益最大的标价方案…… 我看到一个人，正自顾自的玩着**谐音替换**的游戏，即使不小心加多或减少了几个字符也乐此不疲…… 我看到一座城，这里刚刚被灾害侵袭，正在进行紧张的**道路修复**工作…… 我看到一段过往，纵使曾经令我彻夜难眠，但心中的创伤被时间抚平后，终于能看清它们在**岁月**的长河里熠熠生辉…… 最后，当我走到时间的起点，追忆之旅的尽头，我看到了我，那个从联合省选 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。

见上文的**交互格式**。

见上文的**交互格式**。

注意：样例仅作为交互格式展示，不一定具有逻辑。 ### 【数据范围】 本题采用 Subtask 捆绑测试： 对于 $100\%$ 的数据，保证 $2 \le n \le 500$，给定的图是一张连通图。 |测试点编号 |$2 \le n \le$|特殊性质 |分值 | |:--------:|:--------:|:--------:|:--:| |Subtask #1|$5$ |$-$ |$15$| |Subtask #2|$10$ |$-$ |$15$| |Subtask #3|$200$ |保证最短路长度 $> 1$|$15$| |Subtask #4|$200$ |保证$m \ge \frac{n(n-1)}{2}-1$|$5$ | |Subtask #5|$200$ |保证$m = n-1$|$10$| |Subtask #6|$500$ |$-$ |$40$|