== 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, planuieste 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 in care Rick si Morty pleacă să salveze Atlantida, Citadela se află, din nou, in 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. Astfel, 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ă posibilitaţi: arma returnează (0,0) semn că un portal deja există între a si b ori returnează un dublet (x,y) semnalând că un nou portal se va deschide între a si b, în timp ce, portalul dintre x si 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 preveni 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:

Dupa fiecare astfel de query, interactorul va raspunde in stdin astfel:

* "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.

* "0 0": daca muchia (a,b) există deja in arbore.
* "x y": daca 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.

După ce aţi aflat muchile arborelui, afişati "!" pe o singura linie urmat de n-1 linii cu "a b" semnificand ca exista o muchie intre a si b.

După ce aţi aflat muchile arborelui, afişati "!" pe o singură linie urmat de n-1 linii cu "a b" semnificând ca exista o muchie intre a si b.

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:

După fiecare query si dupa ce afisaţi 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:

|_. Limbaj |_. C/C++ |_. Pascal |_. Python |_. Java |_. Rust |
| Header necesar | 0 | 0 |import sys| 0 | use std::io::{self,Write}; |

|_. Stdin |_. Stdout|_. Explicatie|
|2

3 | 0 | Se rezolva primul arbore  |
| 0 | ? 1 3 | Apelam functia pentru muchia 1 3 |
| 0 0 | 0 | Aflam ca muchia 1 3 exista deja in arbore |

3 | 0 | Se rezolvă primul arbore  |
| 0 | ? 1 3 | Apelăm funcţia pentru muchia 1 3 |
| 0 0 | 0 | Aflăm ca muchia 1 3 există deja in arbore |

| 0 | ? 2 3 | 0 |
| 0 0 | 0 | 0 |
| 0 | !
1 3

2 3 | Afisam arborele pentru primul arbore |
| 3 | 0 | Se da al doilea arbore |
| 0 | ? 1 2 | Apelam functia pentru muchia 1 2 |
| 1 3 | 0 | Aflam ca muchia 1 3 a fost stearsa ca sa introducem muchia 1 2|

2 3 | 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, stim ca muchia 2 3 se afla in arbore |

2 3 | Prin eliminare, ştim ca muchia 2 3 se află in arbore |

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