== include(page="template/taskheader" task_id="portale") ==

*Work in progress*
Intr-un alt episod in care Rick si Morty pleaca sa salveze Atlantida, Citadela se afla, din nou, in pericol datorita unui Portal Gun pierdut. Rezistenta Morty-lor, obtinand aceasta arma, planuiesc o revolutie, creand un sistem de portale, sub forma unui arbore ascuns, intre n locatii principale (numerotate de la 1 la n).

Într-un alt episod în care Rick şi Morty pleacă să salveze Atlantida, Citadela se află, din nou, în pericol datorită unui Portal Gun pierdut. Rezistenta Morty-lor, obţinând această armă, plănuieşte o revoluţie, creând un sistem de portale, sub forma unui arbore ascuns, între n locaţii principale (numerotate de la 1 la n).

Stiind ca dimensiunea Citadelei este suprasolicitata, Militia Rick poate schimba fortat reteaua de portaluri pentru a o determina.Asfel, aceasta poate introduce intr-un portal gun coordonatele a doua locatii cheie (a,b) determinand una din doua posibilitati: arma returneaza (0,0) semn ca un portal deja exista intre a si b ori returneaza un dublet (x,y) semnaland ca un nou portal se va deschide intre a si b, in timp ce, portalul dintre x si y se va inchide pentru a preveni aparitia unui ciclu, mentinand forma de arbore a retelei.

Ştiind ca dimensiunea Citadelei este suprasolicitată, Militia Rick poate schimba forţat reţeaua de portaluri pentru a o determina. Astfel, aceasta poate introduce într-un Portal Gun coordonatele a două locaţii cheie (a,b) determinând una din două posibilităţi: arma returnează (0,0) semn că un portal deja există între a şi b ori returnează un dublet (x,y) semnalând că un nou portal se va deschide între a şi b, în timp ce, portalul dintre x şi y se va închide pentru a preveni apariţia unui ciclu, menţinând forma de arbore a reţelei.

Ajutati Militia Rick sa gaseasca sistemul de portaluri pentru a prevenii ranirea inutila a Morty-lor.

Ajutaţi Miliţia Rick să găsească sistemul de portaluri pentru a preveni rănirea inutilă a Morty-lor.

h2. Interactiune

h2. Interacţiune

Initial se citeste din stdin numarul t reprezentand numarul de teste.
Pentru fiecare test se citeste, apoi, n numarul de noduri ale arborelui.

Iniţial se citeşte din stdin numărul T reprezentând numărul de teste.
Pentru fiecare test se citeşte, apoi, N numărul de noduri ale arborelui.

Programul vostru are voie să pună query-uri scriind în standard output:

"? a b" reprezentând introducerea unui dublet in Portal Gun.
Dupa fiecare astfel de query, interactorul va raspunde in stdin astfel:

* "? a b" reprezentând introducerea unui dublet în Portal Gun.

"0 0": daca muchia (a,b) exista deja in arbore.
"x y": daca muchia (a,b) nu exista, dubletul (x,y) reprezinta muchia care se va sterge din graf odata cu adaugarea muchiei (a,b) pentru a pastra forma de arbore.
După ce aţi aflat muchile arborelui, afişati "!\n" urmat de n-1 linii cu "a b" semnificand ca exista o muchie intre a si b.

După fiecare astfel de query, interactorul va răspunde în stdin astfel:

După fiecare query si dupa ce afisati rezultatul unui test, trebuie sa afişaţi '\n' şi să daţi flush la standard output. Pentru a da flush vă puteţi folosi de următorul tabel:

* "0 0": dacă muchia (a,b) există deja în arbore.
* "x y": dacă muchia (a,b) nu există, dubletul (x,y) reprezintă muchia care se va şterge din graf odată cu adăugarea muchiei (a,b) pentru a păstra forma de arbore.

table(example). |_. Limbaj |_. C/C++ |_. Pascal |_. Python |_. Java |_. Rust |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

După ce aţi aflat muchiile arborelui, afişaţi "!" pe o singură linie urmat de n-1 linii cu "a b" semnificând că există o muchie între a şi b.

h2. Date de intrare

După fiecare query şi după ce afişaţi rezultatul unui test, trebuie să afişaţi '\n' şi să daţi flush la standard output. Pentru a da flush vă puteţi folosi de următorul tabel:

Fişierul de intrare $portale.in$ ...

|_. Limbaj |_. C/C++ |_. Pascal |_. Python |_. Java |_. Rust |
| Header necesar | 0 | 0 |import sys| 0 | use std::io::{self,Write}; |
| Functie | fflush(stdout) sau cout.flush() | flush(output) | sys.stdout.flush() | System.out.flush() | io::stdout().flush().unwrap(); |

h2. Date de ieşire

h2. Restricţii şi precizări

În fişierul de ieşire $portale.out$ ...
h2. Restricţii

* *După apelarea query-ului, mai întâi se formează un ciclu, de unde, ulterior, este aleasă muchia care trebuie ştearsă excluzând-o pe cea mai recent adăugată*
* $T = 30$
* $3 ≤ N ≤ 100$

* $... ≤ ... ≤ ...$

h2. Punctare

h2. Exemplu

În cadrul unui test:
 
* Fie Q = numărul de query-uri efectuate;
* Fie Opt = <tex> N(\lceil log_2{N} \rceil - 1) </tex>;
 
Atunci, punctajul pe acel test va fi:

table(example). |_. portale.in |_. portale.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

* <tex>maxim,</tex> dacă <tex>Q $\leq$Opt</tex>;
* <tex>0,</tex> dacă <tex>N*N $\leq$Q</tex>;
* <tex>0.9*(\frac{N*N - Q}{N*N - Opt})^3*maxim,</tex> altfel;

h3. Explicaţie

În cadrul unui subtask, punctajul va fi egal cu punctajul minim dintre testele acestuia:
 
* Subtask $1$ : interactorul este random - $30$ de puncte
* Subtask $2$ : interactorul este adaptiv - $70$ de puncte
 
h2. Exemplu
 
|_. Stdin |_. Stdout|_. Explicaţie|
|2
3 | 0 | Aflăm numărul de teste si numărul de noduri din primul arbore  |
| 0 | ? 1 3 | Muchia 1 3 este adăugată |
| 0 0 | 0 | Operaţia returnează că muchia 1 3 există deja in arbore  |
| 0 | ? 2 3 | 0 |
| 0 0 | 0 | Gun-ul returnează ca muchia 2 3 există deja in arbore  |
| 0 | !
1 3
2 3 | Urmeaza să afişăm muchiile primului arbore |
| 3 | 0 | Se dă al doilea arbore |
| 0 | ? 1 2 | Apelăm funcţia pentru muchia 1 2 |
| 1 3 | 0 | Aflăm ca muchia 1 3 a fost ştearsă ca să introducem muchia 1 2|
| 0 | !
1 2
2 3 | Prin eliminare, ştim că muchia 2 3 se află în arbore |

...

== include(page="template/taskfooter" task_id="portale") ==