#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Perfectly Hidden - Repovive Premier Round 7 | Repovive

20F. Perfectly Hidden

3000 pts2s256 MB

You are given a connected simple undirected graph $G$ with an even number of vertices. The vertices are numbered from $1$ to $n$ .

The interactor has chosen a hidden perfect matching $M$ consisting of edges of $G$ . Thus, $M$ contains exactly $n/2$ edges, and every vertex belongs to exactly one of them.

You may ask about a spanning tree $T$ of $G$ . For this query, the interactor returns

\sum_{(u,v)\in M} \operatorname{dist}_T(u,v),

where $\operatorname{dist}_T(u,v)$ is the number of edges on the unique path between $u$ and $v$ in $T$ .

Your task is to determine the exact hidden matching $M$ . The graph may have several perfect matchings; outputting a perfect matching different from $M$ is not accepted.

You may make at most $n/2$ queries.

Constraints

$2 \le n \le 100$
$n$ is even
$n-1 \le m \le \min\left(1000, \frac{n(n-1)}{2}\right)$
The given graph is simple and connected
The hidden matching is a perfect matching consisting of edges of the given graph

Interactions

To ask a query, print a line containing ?, followed by $n-1$ lines describing the edges of a spanning tree of the given graph:

\begin{array}{l} ? \\ a_1 \quad b_1 \\ a_2 \quad b_2 \\ \vdots \\ a_{n-1} \quad b_{n-1} \end{array}

Every printed edge must belong to the given graph, and the printed edges must form a spanning tree. The interactor replies with one integer: the sum of the distances between the endpoints of all hidden matching edges in this tree.

When you have determined the hidden matching, print a line containing !, followed by its $n/2$ edges:

\begin{array}{l} ! \\ x_1 \quad y_1 \\ x_2 \quad y_2 \\ \vdots \\ x_{n/2} \quad y_{n/2} \end{array}

The matching edges may be printed in any order, and the endpoints of each edge may be printed in either order.

After every query, flush the output buffer. If you read $-1$ at any point, terminate your program immediately. After printing the final answer, terminate without reading another response.

Samples

Input

Explanation

The participant queries the path $1-2-3-4$ . The hidden pairs have distances $1$ and $1$ , so the interactor returns $2$ . The participant then reports the hidden matching.

Interaction

Input

Explanation

For the queried path, the three hidden pairs have distances $1$ , $1$ , and $5$ . Therefore, the interactor returns $7$ .

Interaction

You are given a connected simple undirected graph $G$ with an even number of vertices. The vertices are numbered from $1$ to $n$ .

The interactor has chosen a hidden perfect matching $M$ consisting of edges of $G$ . Thus, $M$ contains exactly $n/2$ edges, and every vertex belongs to exactly one of them.

You may ask about a spanning tree $T$ of $G$ . For this query, the interactor returns

\sum_{(u,v)\in M} \operatorname{dist}_T(u,v),

where $\operatorname{dist}_T(u,v)$ is the number of edges on the unique path between $u$ and $v$ in $T$ .

Your task is to determine the exact hidden matching $M$ . The graph may have several perfect matchings; outputting a perfect matching different from $M$ is not accepted.

You may make at most $n/2$ queries.

$2 \le n \le 100$
$n$ is even
$n-1 \le m \le \min\left(1000, \frac{n(n-1)}{2}\right)$
The given graph is simple and connected
The hidden matching is a perfect matching consisting of edges of the given graph

To ask a query, print a line containing ?, followed by $n-1$ lines describing the edges of a spanning tree of the given graph:

\begin{array}{l} ? \\ a_1 \quad b_1 \\ a_2 \quad b_2 \\ \vdots \\ a_{n-1} \quad b_{n-1} \end{array}

When you have determined the hidden matching, print a line containing !, followed by its $n/2$ edges:

\begin{array}{l} ! \\ x_1 \quad y_1 \\ x_2 \quad y_2 \\ \vdots \\ x_{n/2} \quad y_{n/2} \end{array}

The matching edges may be printed in any order, and the endpoints of each edge may be printed in either order.

After every query, flush the output buffer. If you read $-1$ at any point, terminate your program immediately. After printing the final answer, terminate without reading another response.

The participant queries the path $1-2-3-4$ . The hidden pairs have distances $1$ and $1$ , so the interactor returns $2$ . The participant then reports the hidden matching.

For the queried path, the three hidden pairs have distances $1$ , $1$ , and $5$ . Therefore, the interactor returns $7$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

20F. Perfectly Hidden

Constraints

Interactions

Samples

20F. Perfectly Hidden

Constraints

Interactions

Samples