题目描述

$N$ 頂点の木があり、各頂点には $1,\ldots,N$ と番号が付けられています。
また、各整数 $u,v\,\ (1\ \leq\ u,v\ \leq\ N)$ に対し、頂点 $u,v$ の距離 $d_{u,v}$ を次のように定めます。

• 頂点 $u$ と頂点 $v$ を結ぶ最短パスに含まれる辺の本数

あなたは次のような質問を $0$ 回以上 $2N$ 回以下行うことが出来ます。

• $1\leq\ u,v\ \leq\ N$ かつ $u+v\ >\ 3$ を満たす整数 $u,v$ を指定し、頂点 $u,v$ の距離 $d_{u,v}$ を聞く。

頂点 $1,2$ の距離 $d_{1,2}$ を求めてください。

Input & Output Format

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）である。

まず、あなたのプログラムに標準入力から正の整数 $N$ が与えられる。

$N$

その後、あなたは質問を行うことが出来る。
質問は標準出力に以下の形式で出力せよ(末尾に改行を入れること)。

? $u$ $v$

質問が正当な場合、その質問への答え $d_{u,v}$ が標準入力から与えられる。

$d_{u,v}$

質問の形式が間違っている・質問を規定の回数より多く行った等の理由から質問が不正と判定された場合、質問への答えの代わりに -1 が与えられる。

-1

この時、提出はすでに不正解と判定されている。ジャッジプログラムはこの時点で終了するため、あなたのプログラムも終了するのが望ましい。

答え $d_{1,2}$ が分かったら、標準出力に以下の形式で出力せよ(末尾に改行を入れること)。

! $d_{1,2}$

提示

制約

• $3\ \leq\ N\ \leq\ 100$
• $N$ は整数
• 木はプログラムとジャッジの対話の開始前に決定される

注意点

• 出力を行うたびに標準出力をflushせよ。そうしなかった場合、ジャッジ結果が TLE となる可能性がある。
• 答えを出力したら(または -1 を受け取ったら)直ちにプログラムを正常終了せよ。そうしなかった場合、ジャッジ結果は不定である。
• 不正なフォーマットの出力を行った場合のジャッジ結果は不定である。
• 特に、余計な改行も不正なフォーマットの出力とみなされるので注意せよ。

入出力例

木がこの画像のような時の対話の一例を示します。

入力 出力 説明 3 まず整数 $N$ が与えられます。 ? 1 3 $1$ 回目の質問として頂点 $1,3$ の距離を聞きます。 1 頂点 $1,3$ の距離が与えられます。 ? 2 2 $2$ 回目の質問として頂点 $2,2$ の距離を聞きます。 0 頂点 $2,2$ の距離が与えられます。 ? 2 3 $3$ 回目の質問として頂点 $2,3$ の距離を聞きます。 1 頂点 $2,3$ の距離が与えられます。 ? 3 1 $4$ 回目の質問として頂点 $3,1$ の距離を聞きます。 1 頂点 $3,1$ の距離が与えられます。 ? 3 2 $5$ 回目の質問として頂点 $3,2$ の距離を聞きます。 1 頂点 $3,2$ の距離が与えられます。 ? 2 2 $6$ 回目の質問として頂点 $2,2$ の距離を聞きます。 0 頂点 $2,2$ の距離が与えられます。 ! 2 頂点 $1,2$ の距離を回答し、終了します。実際に木の頂点 $1,2$ の距離は $2$ であるため AC が得られます。