Secret Trail - Repovive Premier Round 6 | 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$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

16F. Secret Trail

Constraints

Interactions

Samples

16F. Secret Trail

Constraints

Interactions

Samples