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

$ curl repovive.com/contests/16/problems/F

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Secret Trail - Repovive Premier Round 6 | Repovive | Repovive

16F. Secret Trail

2750 pts2s256 MB

This is an interactive problem.

There is a hidden simple undirected graph with vertices $1,2,\ldots,n$ .

The graph is connected. Also, among every $4$ distinct vertices, there is at least one pair of adjacent vertices.

Your goal is to find a simple path containing at least $\left\lfloor 2n/3 \right\rfloor + 1$ vertices.

You may ask at most $2n$ queries.

In one query, you choose a vertex $v$ and a non-empty set $S$ of vertices. The interactor returns one vertex from $S$ that is adjacent to $v$ in the hidden graph. If there is no such vertex, the interactor returns $0$ .

If there are several valid vertices that can be returned, the interactor may return any of them.

The hidden graph is fixed before the interaction starts.

Constraints

$1 \le n \le 100$
The hidden graph is simple and undirected.
The hidden graph is connected.
Among every $4$ distinct vertices, there is at least one edge.
You may ask at most $2n$ queries.

Interactions

The interaction starts with the interactor printing one integer $n$ .

You may ask at most $2n$ queries.

To ask a query, print a line in the following format:

$? \ v \ k \ s_1 \ s_2 \ \ldots \ s_k$

Here $1 \le v \le n$ , $1 \le k \le n-1$ , and $s_1,s_2,\ldots,s_k$ must be distinct vertices different from $v$ .

After this, the interactor prints one integer $u$ .

If there is at least one vertex in $S=\{s_1,s_2,\ldots,s_k\}$ adjacent to $v$ , then $u$ is one such vertex. If there are several possible choices, the interactor may return any of them.

If no vertex in $S$ is adjacent to $v$ , then $u=0$ .

To give the final answer, print a line in the following format:

$! \ \ell \ p_1 \ p_2 \ \ldots \ p_\ell$

The vertices $p_1,p_2,\ldots,p_\ell$ must be distinct, every two consecutive vertices must be adjacent in the hidden graph, and $\ell$ must be at least $\left\lfloor 2n/3 \right\rfloor+1$ .

After printing each query or the final answer, flush the output.

Samples

Input

Explanation

In this sample, the hidden graph has edges $(1,2)$ and $(2,3)$ .

The first line of the input gives $n=3$ . After the query $? \ 1 \ 1 \ 2$ , the interactor returns $2$ . After the query $? \ 2 \ 1 \ 3$ , the interactor returns $3$ .

The user asks $2$ queries.

The final answer gives the path $1,2,3$ . This path has $3$ vertices, while the required length is at least $\left\lfloor \frac{2 \times 3}{3} \right\rfloor+1 = 3$ .

Interaction

Input

Explanation

In this sample, the hidden graph has edges $(1,2)$ , $(1,3)$ , $(1,6)$ , $(2,3)$ , $(2,4)$ , $(2,5)$ , $(2,6)$ , and $(3,6)$ .

The first line of the input gives $n=6$ . The next lines are the interactor responses to the user's queries, in order: $2$ , $3$ , $6$ , $0$ , $0$ , and $4$ .

The user asks $6$ queries.

The final answer gives the path $4,2,1,3,6$ . This path has $5$ vertices, while the required length is at least $\left\lfloor \frac{2 \times 6}{3} \right\rfloor+1 = 5$ .

Interaction

? 1 5 2 3 4 5 6

? 2 4 3 4 5 6

? 3 3 4 5 6

? 6 2 4 5

? 3 2 4 5

? 2 2 4 5

! 5 4 2 1 3 6

This is an interactive problem.

There is a hidden simple undirected graph with vertices $1,2,\ldots,n$ .

The graph is connected. Also, among every $4$ distinct vertices, there is at least one pair of adjacent vertices.

Your goal is to find a simple path containing at least $\left\lfloor 2n/3 \right\rfloor + 1$ vertices.

You may ask at most $2n$ queries.

If there are several valid vertices that can be returned, the interactor may return any of them.

The hidden graph is fixed before the interaction starts.

$1 \le n \le 100$
The hidden graph is simple and undirected.
The hidden graph is connected.
Among every $4$ distinct vertices, there is at least one edge.
You may ask at most $2n$ queries.

The interaction starts with the interactor printing one integer $n$ .

You may ask at most $2n$ queries.

To ask a query, print a line in the following format:

$? \ v \ k \ s_1 \ s_2 \ \ldots \ s_k$

Here $1 \le v \le n$ , $1 \le k \le n-1$ , and $s_1,s_2,\ldots,s_k$ must be distinct vertices different from $v$ .

After this, the interactor prints one integer $u$ .

If there is at least one vertex in $S=\{s_1,s_2,\ldots,s_k\}$ adjacent to $v$ , then $u$ is one such vertex. If there are several possible choices, the interactor may return any of them.

If no vertex in $S$ is adjacent to $v$ , then $u=0$ .

To give the final answer, print a line in the following format:

$! \ \ell \ p_1 \ p_2 \ \ldots \ p_\ell$

The vertices $p_1,p_2,\ldots,p_\ell$ must be distinct, every two consecutive vertices must be adjacent in the hidden graph, and $\ell$ must be at least $\left\lfloor 2n/3 \right\rfloor+1$ .

After printing each query or the final answer, flush the output.

In this sample, the hidden graph has edges $(1,2)$ and $(2,3)$ .

The first line of the input gives $n=3$ . After the query $? \ 1 \ 1 \ 2$ , the interactor returns $2$ . After the query $? \ 2 \ 1 \ 3$ , the interactor returns $3$ .

The user asks $2$ queries.

The final answer gives the path $1,2,3$ . This path has $3$ vertices, while the required length is at least $\left\lfloor \frac{2 \times 3}{3} \right\rfloor+1 = 3$ .

In this sample, the hidden graph has edges $(1,2)$ , $(1,3)$ , $(1,6)$ , $(2,3)$ , $(2,4)$ , $(2,5)$ , $(2,6)$ , and $(3,6)$ .

The first line of the input gives $n=6$ . The next lines are the interactor responses to the user's queries, in order: $2$ , $3$ , $6$ , $0$ , $0$ , and $4$ .

The user asks $6$ queries.

The final answer gives the path $4,2,1,3,6$ . This path has $5$ vertices, while the required length is at least $\left\lfloor \frac{2 \times 6}{3} \right\rfloor+1 = 5$ .

	#	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

16F. Secret Trail

Constraints

Interactions

Samples

16F. Secret Trail

Constraints

Interactions

Samples