POLSKI SPOJ

Jaś postanowił zorganizować imprezę z cyklu wiosenne marsze na orientacje. Wziąwszy mapę okolicy wyznaczył n punktów terenowych, które ponumerował od 1 do n. Projektowane trasy powinny zaczynać się w jednym z punktów i kończyć w innym, przechodząc przez dowolną liczbę pozostałych punktów. Żadne dwie trasy nie mogą zawierać wspólnego fragmentu (bezpośredniego połączenia między tą samą parą punktów). Liczba tras zależy od liczby uczestników, ale na pewno będzie mniejsza niż n. Pomoż Jasiowi wyznaczyć trasy!

Wejście

W pierwszej linii podana jest liczba zestawów t (t<=100). Opis każdego zestawu rozpoczyna się od podania w jednej linii liczby punktów terenowych n <= 1000 oraz wymaganej ilości tras k < n. Następnie w k kolejnych liniach podane zostały pary punktów pomiędzy którymi należy zbudować trasę. Pary punktów mogą się powtarzać.

Wyjście

Dla i-tego zestawu, jeżeli nie jest możliwe zaprojektowanie tras pomiędzy podanymi parami punktów, wydrukuj na wyjście napis:"zestaw i N". Jeżeli natomiast jest możliwe zaprojektowanie tras, wypisz "zestaw i T", nastepnie w kolejnych k linijkach opisz każdą z tras zaczynając od początkowego punktu do ostatniego włącznie, poprzedzając opis długością trasy, tzn. d p₁ ... p_d.

Przykład

Wejście:
2
4 3
1 2
1 2
1 3
3 2
1 2
2 3

Wyjście:
zestaw 1 T
2 1 2
3 1 4 2
2 1 3
zestaw 2 T
2 1 2
2 2 3