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$

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

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

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