Background

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.”

Problem Description

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.

Input Format

See the Interaction Format above.

Output Format

See the Interaction Format above.

3

1

2

? 1 2

? 2 3

! 1

5

1

1

1

1

? 1 2

? 2 3

? 3 4

? 4 5

! 4

Hint

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.

Translated by ChatGPT 5