Il existe un graphe simple non orienté à $n$ sommets. Ce graphe possède une propriété supplémentaire :

• Tout sous-graphe induit contient un sommet de degré au plus $k$.

Vous devez trouver ce graphe caché. Vous pouvez vérifier pour n'importe quel sous-ensemble s'il s'agit d'un ensemble indépendant. Si ce n'est pas le cas, nous vous montrerons une arête dont les deux extrémités se trouvent à l'intérieur de ce sous-ensemble.

Nous ne modifierons pas le graphe pendant l'interaction, vous pouvez donc supposer qu'il est fixe. Cependant, nous pouvons choisir n'importe quelle arête à l'intérieur du sous-graphe induit à montrer. En d'autres termes, dans tous les tests, le graphe est fixe, mais l'interacteur est adaptatif.

Vous devez deviner le graphe en au plus $2nk + n$ requêtes.

Protocole d'interaction

L'interaction commence par une ligne contenant un entier $n$ : le nombre de sommets dans le graphe caché ($2 \le n \le 2000$).

L'entier $k$ n'est pas donné, mais il satisfait la contrainte $1 \le k < n$, $nk \le 2000$.

Après cela, vous pouvez effectuer des requêtes.

Pour effectuer une requête, affichez une ligne contenant « ? $k$ » ($1 \le k \le n$) suivie de $k$ entiers distincts $v_1, v_2, \dots, v_k$ ($1 \le v_i \le n$). Séparez les entiers consécutifs par des espaces simples. Ensuite, videz le tampon de sortie (flush).

Après chaque requête, lisez une ligne avec deux entiers $i, j$. S'il n'y a pas d'arêtes dans le sous-graphe induit par $v_1, v_2, \dots, v_k$, alors $i = j = -1$. Sinon, $i \neq j$, $i \in \{v_1, \dots, v_k\}$, $j \in \{v_1, \dots, v_k\}$, et il existe une arête reliant $i$ et $j$ dans le graphe.

Lorsque vous avez trouvé le graphe, affichez sur la première ligne « ! $m$ ». Les $m$ lignes suivantes doivent contenir la description des arêtes du graphe, chacune devant contenir deux entiers $u, v$ ($1 \le u, v \le n$), désignant les indices des sommets reliés par une arête.

Votre solution recevra un verdict Wrong Answer ou Time Limit Exceeded si vous effectuez plus de $2nk + n$ requêtes. Votre solution recevra un verdict Idleness Limit Exceeded si vous n'affichez rien ou si vous oubliez de vider le tampon de sortie.

Pour vider le tampon (flush), vous devez effectuer l'opération suivante juste après avoir affiché une requête et un saut de ligne :

• fflush(stdout) ou cout.flush() en C++ ;
• System.out.flush() en Java ;
• flush(output) en Pascal ;
• stdout.flush() en Python ;
• consultez la documentation pour les autres langages.

Exemples

Entrée 1

3
1 2
2 3
1 3

Sortie 1

? 2 1 2
? 2 2 3
? 2 1 3
! 3
1 2
2 3
1 3