201422: [AtCoder]ARC142 C - Tree Queries

Problem Statement

There is a tree with $N$ vertices, numbered $1, \ldots, N$.
For each pair of integers $u,v\, (1 \leq u,v \leq N)$, the distance $d_{u,v}$ between Vertices $u, v$ is defined as the following.

• The number of edges contained in the shortest path connecting Vertices $u$ and $v$.

You are allowed to ask between $0$ and $2N$ questions (inclusive) in the following form.

• Ask the distance $d_{u,v}$ between Vertices $u,v$ for integers $u,v$ of your choice such that $1\leq u,v \leq N$ and $u+v>3$.

Find the distance $d_{1,2}$ between Vertices $1,2$.

Constraints

• $3 \leq N \leq 100$
• $N$ is an integer.
• The tree is determined before the start of the interaction between your program and the judge.

Input and Output

This is an interactive task, in which your program and the judge interact via input and output.

First, your program is given a positive integer $N$ from Standard Input:

$N$

Then, you get to ask questions.
A question should be printed in the following format (with a newline at the end):

? $u$ $v$

If the question is valid, the response $d_{u,v}$ is given from Standard Input:

$d_{u,v}$

If the question is judged invalid because, for example, it is malformed or you have asked too many questions, you get -1 instead of the response:

-1

At this point, your submission is already judged incorrect. The judge's program then terminates; yours should too, desirably.

When you find the answer $d_{1,2}$, print it to Standard Output in the following format (with a newline at the end):

! $d_{1,2}$

Notices

• Flush Standard Output after each output. Otherwise, you might get the TLE