h2. Interactiune

Initial se citeste din stdin numarul t reprezentand numarul de teste.
Pentru fiecare test se citeste, apoi, n numarul de noduri ale arborelui.
Programul vostru are voie să pună query-uri scriind în standard output:
 
"? 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.
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:

h2. Date de intrare