Énoncé
Bien sûr, c'est un problème.
Il s'agit d'un problème interactif. On vous donne un graphe non orienté inconnu ayant $n$ sommets et $m$ arêtes, sans arêtes multiples ni boucles. À chaque fois, vous pouvez poser la question suivante à la bibliothèque d'interaction :
- Étant donné un ensemble de sommets $S \subseteq \{1, 2, \dots, n\}$, demander si cet ensemble de sommets est un ensemble indépendant.
Ici, un ensemble indépendant signifie qu'il n'y a aucune arête entre deux sommets distincts quelconques de l'ensemble $S$.
Votre objectif est de déterminer l'ensemble complet des arêtes du graphe en utilisant au plus $M = n + m(2 + \lceil\log_2 n\rceil)$ requêtes.
Notez que vous ne connaissez pas la valeur de $m$ à l'avance et que la bibliothèque d'interaction est adaptative, c'est-à-dire que le graphe n'est pas fixé dès le départ, mais sera ajusté dynamiquement en fonction de vos requêtes.
Entrée
La première ligne contient un entier $T$ ($1 \le T \le 100$), désignant le nombre de cas de test.
Pour chaque cas de test, une ligne contient un entier $n$ ($1 \le n \le 500$), désignant le nombre de sommets du graphe non orienté inconnu.
Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $500$, que $0 \le m \le 500$ et que la somme de $m$ ne dépasse pas $500$.
Interaction
Lorsque vous devez poser une requête, affichez une ligne :
? k v_1 v_2 ... v_k
où $k$ désigne la taille de l'ensemble de sommets, et $v_1, v_2, \dots, v_k$ sont les indices des sommets de l'ensemble que vous interrogez, tous deux à deux distincts.
La bibliothèque d'interaction renverra un entier : $1$ si l'ensemble de sommets est un ensemble indépendant ; $0$ sinon.
Lorsque vous avez déterminé toutes les arêtes du graphe, affichez une ligne :
! m u_1 v_1 u_2 v_2 ... u_m v_m
où $m$ est le nombre d'arêtes dans le graphe non orienté, et $(u_i, v_i)$ représente une arête du graphe. Vous pouvez afficher les arêtes dans n'importe quel ordre.
Après cela, s'il ne reste plus de cas de test, votre programme doit se terminer immédiatement ; sinon, il doit passer au cas de test suivant.
Exemples
Entrée 1
1 4 0 1 0 0 1 0
Sortie 1
? 2 1 2 ? 2 1 3 ? 2 1 4 ? 2 2 3 ? 2 2 4 ? 2 3 4 ! 4 1 2 2 3 3 4 1 4
Note
L'exemple illustre un processus interactif consistant à demander individuellement si chaque arête existe.