Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PZPI1 - Marsze na orientację

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 p1 ... pd.

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


Dodane przez:mima
Data dodania:2005-05-20
Limit czasu wykonania programu:10s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:-
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.