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 in Portal Gun.

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