P16824 [AFOI 2025] A2. Reminiscence (Hard Version)

I often reminisce about the past. Although the sharp edges of the past once hurt me deeply... When I travel upstream along the long river of time, I see those suffocating memories freeze again in my mind, turning into white clouds in the sky. I see a tree, stretching its branches as time goes by, searching for the **value of a tree** among changing vertex weights... I see a shop, where people are thinking, thinking about the best pricing plan to maximize profit during a **clearance sale** of candy... I see a person, playing a **homophone replacement** game on their own, happily doing so even if they accidentally add or remove a few characters... I see a city, just hit by a disaster, carrying out intense **road repair** work... I see a piece of the past. Even though it once kept me awake all night, after time smooths out the wounds in my heart, I can finally see them shining brightly in the long river of **years**... Finally, when I reach the starting point of time, the end of this journey of reminiscence, I see myself, the me who walked out of the Joint NOI Qualifier 2025 exam room. I see the helplessness on his face... I hear him say to me... Or rather, I hope that one day, he can smile and say to me... “I often **reminisce** about the past.”

**This is an interactive problem.** **This is the hard version of the problem. The difference between the two versions is that, in this problem, you have $n$ chances to “reminisce”.** There is an undirected connected graph with $n$ vertices and $m$ edges (all edge weights are $1$). Unfortunately, you forgot the shortest path from $1$ to $n$. You have $n$ chances to “reminisce”. Each time you “reminisce”, you can recall the shortest path length between two vertices. Since you really cannot recall the shortest path length from $1$ to $n$, you need to find the shortest path from $1$ to $n$ **without** directly “reminiscing” the shortest path between $1$ and $n$. However, reminiscence is like entering a dream: if it is too clear, it cannot satisfy your fantasies; if it is too vague, it falls into nothingness. To meet your strict sense of beauty, **in this problem, your output is considered correct as long as the absolute difference between your output and the standard answer does not exceed $1$**. ### Interaction Format First, you can read a positive integer $n$, which denotes the number of vertices. **Note: you cannot read and do not need to read the number of edges $m$!** When you want to “reminisce”, output one line `? x y` to ask for the shortest path length from $x$ to $y$. You must ensure that $1 \le x \le y \le n$ and $(x,y) \not= (1,n)$. If your query does not satisfy the above requirements or the number of queries exceeds $n$, the interactive judge will return WA; otherwise, the interactive judge will output a positive integer representing the shortest path length. When you have determined the answer, you can output one line `! x` to report your answer. If your answer differs from the standard answer by no more than $1$, the interactive judge will return AC; otherwise, it will return WA.

See the **Interaction Format** above.

See the **Interaction Format** above.

Note: the sample is only for demonstrating the interaction format and may not be logically valid. ### Constraints This problem uses bundled Subtasks. For $100\%$ of the testdata, it is guaranteed that $2 \le n \le 500$, and the given graph is connected. |Subtask ID|$2 \le n \le$|Special Property|Score| |:--------:|:--------:|:--------:|:--:| |Subtask #1|$5$|$-$|$15$| |Subtask #2|$10$|$-$|$15$| |Subtask #3|$200$|The shortest path length is guaranteed to be $> 1$|$15$| |Subtask #4|$200$|Guaranteed that $m \ge \frac{n(n-1)}{2}-1$|$5$| |Subtask #5|$200$|Guaranteed that $m = n-1$|$10$| |Subtask #6|$500$|$-$|$40$| Translated by ChatGPT 5