Divine

Stich vrea să cartografieze arhipelagul Hawaii folosind scanerul navei sale. Arhipelagul este format din $N$ insule, numerotate cu numere naturale de la $0$ la $N - 1$, și $M$ poduri ce conectează câte două insule. În ultima misiune, scanerul s-a defectat, așa că poate să proceseze doar următorul tip de comandă: Stich alege o mulțime de insule, iar scanerul îi spune numărul maxim de insule dintre cele selectate ce pot fi vizitate plecând dintr-o insulă din multime, folosind doar podurile existente și nepărăsind niciodată mulțimea pe parcursul deplasării. Ajutați-l pe Stich să cartografieze arhipelagul, folosind de un număr relativ mic de ori scanerul!

Mai formal, se dă un graf neorientat $G$ cu $N$ noduri și $M$ muchii. La o interogare, concurentul va alege o submulțime de noduri din $G$ și va afla numărul maxim de noduri dintr-o componentă conexă a subgrafului format din nodurile submulțimii și muchiile dintre ele. Se cere aflarea grafului $G$ într-un număr relativ mic de interogații. Atenție! Inițial, concurentul știe doar valoarea lui $N$, nu și pe cea a lui $M$!

Protocol de interacțiune

Problema este interactivă. Concurentul va implementa functia solve cu urmatoarea semnatura:

void solve (int N, int subtask_id);

Parametrul $N$ reprezintă numărul de noduri din $G$. Parametrul $subtask\_id$ reprezintă indicele subtaskului pe care se rulează sursa concurentului (un număr întreg între $1$ și $7$, inclusiv).

Concurentul se poate folosi de funcțiile query și answer cu următoarele semnături:

int query (const std::vector<int>& nodes);
void answer (const std::vector<std::pair<int, int>>& ans);

Funcția query reprezintă o interogare. Parametrul nodes conține indicii nodurilor pe care este realizată interogarea. Funcția întoarce mărimea componentei conexe maxime, așa cum este specificat în enunț. Nodurile se pot regăsi în orice ordine în $nodes$.

Funcția answer va fi apelată o singură dată de către concurent, după ce acesta a găsit muchiile grafului $G$. Parametrul $ans$ conține muchiile găsite de concurent, în orice ordine. Ordinea nodurilor în cadrul fiecărei muchii nu este importantă.
Concurentul NU va implementa o funcție main.

Restricții

Fie $Q$ numărul de interogări pe care le face concurentul și $R = \frac{Q}{M}$.

• $N = 512$.
• $N - 1 \leq M \leq 8192$.

Subtask 1 (3 puncte)

• $G$ este un lanț.
• Dacă $R \leq 35$, atunci se acordă tot punctajul subtaskului.

Subtask 2 (1 punct)

• $G$ este un graf stea.
• Punctarea este aceeași ca la subtaskul precedent.

Subtask 3 (30 puncte)

• $G$ este un arbore.
• Toate nodurile lui $G$ au gradul cel mult $3$.
• Dacă $R \leq 15$, atunci se acordă tot punctajul subtaskului.
• Dacă $15 < R \leq 25$, atunci se acordă $(115 - R)\%$ din punctajul subtaskului.
• Dacă $25 < R \leq 35$, atunci se acordă $(190 - 4R)\%$ din punctajul subtaskului.
• Dacă $35 < R$ si $Q \leq 130816$, atunci se acordă $1$ punct pentru subtask.

Subtask 4 (30 puncte)

• $G$ este un arbore.
• Punctarea este aceeași ca la subtaskul precedent.

Subtask 5 (3 puncte)

• $G$ este un ciclu.
• Punctarea este aceeași ca la subtaskul precedent.

Subtask 6 (16 puncte)

• Toate nodurile lui $G$ au gradul cel mult $10$.
• Dacă $R \leq 11$, atunci se acordă tot punctajul subtaskului.
• Dacă $11 < R \leq 12$, atunci se acordă $75\%$ din punctajul subtaskului.
• Dacă $12 < R \leq 13$, atunci se acordă $50\%$ din punctajul subtaskului.
• Dacă $13 < R \leq 25$, atunci se acordă $25\%$ din punctajul subtaskului.

Subtask 7 (17 puncte)

• Nu există restricții suplimentare.
• Punctarea este aceeași ca la subtaskul precedent.

Exemple

Comisie: $N = 3, subtask\_id = 1$
Concurent: Query: $\{0, 1, 2\}$
Comisie: $3$
Concurent: Query: $\{0, 1\}$
Comisie: $2$
Concurent: Query: $\{2, 0\}$
Comisie: $2$
Concurent: Query: $\{1, 2\}$
Comisie: $1$
Concurent: Answer: $\{(0,1), (0,2)\}$