POLSKI SPOJ

Pewnego upalnego dnia do miasteczka, w którym mieszkał Jasio, przyjechały tajemnicze samochody z ofertą sprzedaży nowych cudownych lodów. Kto tylko raz spróbował owych lodów posiadł natychmiast rzadką do tej pory umiejętność rozwiązywania trudnych zadań matematycznych. Ponieważ wszyscy chcieli zostać matematykami, ustawiały sie gigantyczne kolejki i tu i ówdzie lodów zaczynało brakować. Władze miasteczka postanowiły zaprowadzić porządek i ustaliły co następuje:

• na każdym skrzyżowaniu będą sprzedawane lody,
• mieszkańcy każdej ulicy muszą wspólnie ustalić, do którego skrzyżowania się udadzą,
• mieszkańcy z dokładnie połowy ulic sąsiednich do danego skrzyżowania muszą się przy nim zebrać.

Pomóż mieszkańcom miasta podjąć decyzję, na których skrzyżowaniach, mieszkańcy których ulic mają się zebrać.

Wejście

W pierwszej linii podana jest liczba zestawów t (t <= 10). Opis każdego zestawu rozpoczyna się od podania w pierwszej linii liczby miejsc (skrzyżowań), z których będą sprzedawane lody, n <= 5000 oraz połowy liczby ulic przylegających do każdego skrzyżowania (dla wszystkich skrzyżowań identyczna liczba) k < 100. Następnie w n*k kolejnych liniach podane zostały ulice identyfikowane przez ograniczające je skrzyżowania.

Wyjście

Dla i-tego zestawu, jeżeli nie jest możliwe przydzielenie mieszkańców do skrzyżowań, wydrukuj na wyjście napis:"zestaw i N". Jeżeli natomiast jest możliwe ustawienie mieszkańców zgodne z zasadami, wypisz "zestaw i T", w linijce j podaj dokładnie k liczb całkowitych oznaczających drugie końce wybranych ulic.

Przykład

Wejście:
2
4 1
1 2
2 3
3 4
4 1
8 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 5
5 2
2 6
6 1
3 7
7 4
4 8
8 3
8 1

Wyjście:
zestaw 1 T
2
3
4
1
zestaw 2 T
5 6
1 6
2 8
3 8
2 4
5 7
3 4
1 7