Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Difficulté: [afficher] Interactif Hackable ✓
Statistiques

Descrizione

Certo, questo è un problema.

Questo è un problema interattivo. Ti viene dato un grafo non orientato sconosciuto con $n$ vertici e $m$ archi, senza archi multipli né cappi. Ogni volta puoi porre alla libreria di interazione la seguente domanda:

  • Dato un insieme di vertici $S \subseteq \{1, 2, \dots, n\}$, chiedi se questo insieme di vertici è un insieme indipendente.

Qui, insieme indipendente significa che non c'è alcun arco tra due vertici distinti qualsiasi nell'insieme $S$.

Il tuo obiettivo è determinare l'intero insieme di archi del grafo usando non più di $M = n + m(2 + \lceil\log_2 n\rceil)$ interrogazioni.

Nota che non conosci il valore di $m$ in anticipo e la libreria di interazione è adattiva, cioè il grafo non è fissato fin dall'inizio, ma verrà adattato dinamicamente in base alle tue interrogazioni.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 100$), che indica il numero di casi di test.

Per ogni caso di test, una riga contiene un intero $n$ ($1 \le n \le 500$), che indica il numero di vertici del grafo non orientato sconosciuto.

È garantito che la somma di $n$ su tutti i casi di test non supera $500$, $0 \le m \le 500$ e la somma di $m$ non supera $500$.

Interazione

Quando devi effettuare un'interrogazione, stampa una riga:

? k v_1 v_2 ... v_k

dove $k$ indica la dimensione dell'insieme di vertici e $v_1, v_2, \dots, v_k$ sono gli indici dei vertici nell'insieme che stai interrogando, tutti distinti a due a due.

La libreria di interazione restituirà un intero: $1$ se l'insieme di vertici è un insieme indipendente; $0$ altrimenti.

Quando hai determinato tutti gli archi del grafo, stampa una riga:

! m u_1 v_1 u_2 v_2 ... u_m v_m

dove $m$ è il numero di archi nel grafo non orientato e $(u_i, v_i)$ rappresenta un arco nel grafo. Puoi stampare gli archi in qualsiasi ordine.

Dopodiché, se non ci sono altri casi di test, il tuo programma deve terminare immediatamente; altrimenti deve procedere al caso di test successivo.

Esempi

Input 1

1
4
0
1
0
0
1
0

Output 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'esempio mostra un processo interattivo in cui si chiede singolarmente se ciascun arco esiste.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1842EditorialOpenNew Editorial for Problem #18123wangmaruiView

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.