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

Î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).

Î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).

Ş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 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.

Ş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.

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

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

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

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

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

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

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

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

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ă 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.

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:

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:

|_. 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. Restricţii si precizări

h2. Restricţii şi precizări

* *După apelarea query-ului, mai intai se formează un ciclu, de unde, ulterior, este aleasă muchia care trebuie ştearsă excluzând-o pe cea mai recent adaugata*
* T=30

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

In cadrul unui test:

În cadrul unui test:

* Fie Q = numarul de query-uri efectuate;
* Fie  Opt = <tex> N(log_2{N}-1) </tex>;

* 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:

* <tex>maxim</tex>, daca Q <= Opt;
* 0, daca N*N < Q
* <tex>0.9*(\frac{N*N - Q}{N*N - Opt})^3*maxim</tex>

* <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;

In cadrul unui subtask, punctajul va fi egal cu punctajul minim dintre testele acestuia:

Î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

* Subtask $1$ : interactorul este random - $30$ de puncte
* Subtask $2$ : interactorul este adaptiv - $70$ de puncte

h2. Exemplu

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

|_. Stdin |_. Stdout|_. Explicaţie|

|2

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 |

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 | 0 |

| 0 0 | 0 | Gun-ul returnează ca muchia 2 3 există deja in arbore  |

| 0 | !
1 3

2 3 | Afişăm muchiile primului arbore |

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 ca muchia 2 3 se află in arbore |

2 3 | Prin eliminare, ştim că muchia 2 3 se află în arbore |

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