Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Interactif
Statistiques

Description

There is a directed graph on $n$ vertices numbered $1$ through $n$. For each vertex $1 \le i \le n$, the out-degree of vertex $i$ is at most one; thus we may describe the graph using an array $p_i$, where $p_i = 0$ if the out-degree of vertex $i$ is zero, and otherwise $1 \le p_i \le n$, $p_i \ne i$, and there is a directed edge from $i$ to $p_i$. There are no directed cycles in the graph, so from any vertex $i$, the path formed by repeatedly moving to the next vertex along directed edges will eventually terminate at a vertex of out-degree zero.

Initially, there is a wooden checker on one of the vertices. When you clap your hands, if the checker is on a vertex $i$ with $p_i$ non-zero, it will move to vertex $p_i$; otherwise it does not move. However, you cannot see where the checker is at all — the only operation you can perform is to choose a subset of vertices, place the checker on one of your chosen vertices, clap your hands a number of times, and observe whether the checker ends up on one of your chosen vertices. Even the initial placement of the checker and the number of times you clap your hands are chosen by an interactor: you only get to choose the subset of vertices, and observe the maximum number of times you can clap your hands such that the checker is able to start on one of your chosen vertices and end on one of your chosen vertices.

You would like to add a single edge from $x$ to $y$ ($1 \le x, y \le n$, $x \ne y$, and $p_x = 0$, i.e., you may set $p_x = y$), so that you will be able to clap your hands even more times on the entire graph than before. Still, adding the edge may not create any directed cycles in the graph.

Find any such edge that you can add by querying for the maximum number of times you can clap your hands on at most $n$ subsets of vertices, or determine that it is impossible to add such an edge.

Input

The first line of the input contains a single integer $n$ ($1 \le n \le 1000$).

Interaction

To make a query, print a single line of the form $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, where $1 \le k \le n$, and $1 \le u_i \le n$ are pairwise distinct vertices in your chosen subset. Then read a single line containing a single integer: the maximum number of times you can clap your hands such that the checker is able to start on one of your chosen vertices and end on one of your chosen vertices. You may make at most $n$ queries.

After you have determined the edge you would like to add, print a single line of the form $\texttt{! } x \text{ } y$, where $1 \le x, y \le n$ are the endpoints of the directed edge you would like to add. If there are multiple solutions, you may output any of them.

If it is impossible to add such an edge, print $-1 \text{ -1}$ instead of the endpoints of the edge.

Your solution must terminate immediately after outputting the answer.

Flush the output after each query you make.

The interactor is not adaptive; the graph is fixed in advance.

Example

6

2

1

2
? 4 1 2 3 4

? 2 5 6

? 3 4 5 6

! 5 1

Note

problem_17169_c1d82052e4ed01f4f4f5920c82dcbcb1.png

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1220EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.