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.

După fiecare astfel de query, interactorul va răspunde în stdin astfel:
* "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 muchiile arborelui, afişaţi "!" pe o singură linie urmat de n-1 linii cu "a b" semnificând ca exista o muchie între a şi 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 ş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:

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 adăugată*

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

| 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ă în arbore |

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

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