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

BFN5 - Król Piotruś w Parku Mamutów

Park w Bajtlandii jest dosyć nietypowym miejscem. W przeciwieństwie do innych parków, zamieszkałych przez wiewiórki i inne małe zwierzątka, park bajtlandzki szczyci się swoim pokaźnym stadem mamutów. Niestety, ich obecność prowadzi czasem do pewnych komplikacji...

Pewnego dnia Król Bitlandii, Piotruś I Malutki, składał wizytę w Bajtlandii i zapragnął odwiedzić słynny mamuci park. Ponieważ mamuty bywają nieco nieprzewidywalne i nie znają się kompletnie na dworskiej etykiecie, należało je stosownie uwiązać. Jednak skuteczne wiązanie mamutów nie jest tak łatwe, jak mogłoby się wydawać.

Park złożony jest z małych polanek połączonych alejkami, a na każdej polance stoi mamut. Z powodu braku solidnych drzew w parku, nie da się mamutów wiązać z niczym innym, oprócz innych mamutów. Okazuje się, że uwiązanie mamuta zbyt małą liczbą lin może prowadzić do niebezpiecznych skutków, więc przyjęto, że każdy mamut musi być przymocowany 2 linami do dokładnie 2 innych mamutów (tym sposobem wszystkie zwierzęta nie stanowią zagrożenia, a zarazem nie mają poczucia krzywdy). Liny łączące mamuty muszą biec wzdłuż alejek parku i mogą mieć długość co najwyżej 3 alejek (zakłada się, że lina nie dotyka mamutów stojących na polankach innych niż końcowe). Liny trzeba prowadzić tak, by co najwyżej dwie liny biegły jedną alejką, bo inaczej wszystko mogłoby się straszliwie poplątać.

Twoim zadaniem jest określić, w jaki sposób należy powiązać linami mamuty na czas wizyty Króla Piotrusia (lub stwierdzić, że takie powiązanie jest niemożliwe).

Wejście

Pierwsza linia wejścia zawiera liczbę całkowitą t (t<=100). Na kolejnych liniach podane jest t przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera dwie liczby całkowite n m, oddzielone spacją, oznaczające odpowiednio liczbę polanek (na każdej znajduje się mamut) oraz liczbę alejek w parku (1<=n,m<=20000).

Na kolejnych m liniach podane są po dwie liczby całkowite ai bi, które oznaczają, że polanki o numerach ai oraz bi są połączone alejką (1<=ai,bi<=n). Zakładamy, że alejki się nigdy nie przecinają poza polankami na ich końcach (jednak może się zdarzyć, że jedna alejka w pewnym miejscu przebiega nad lub pod inną alejką).

Wyjście

Dla danego przypadku testowego wypisz linię ze słowem TAK, jeżeli istnieje rozwiązanie postawionego problemu, lub słowo NIE, jeżeli takiego rozwiązania nie ma. Jeżeli rozwiązanie istnieje, kolejne n linii powinno zawierać opisy poszczególnych lin łączących mamuty. Każda linia powinna zacząć się od długości liny l, mierzonej w alejkach (l=1 lub l=2 lub l=3); następnie należy podać dokładnie l+1 liczb całkowitych określających numery polanek, przez które kolejno przebiega lina.

Przykład

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

Wyjście:
TAK
1 1 2
1 1 3
2 2 1 3
NIE

Dodane przez:adrian
Data dodania:2005-05-08
Limit czasu wykonania programu:4.320s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:I Pomorskie Zawody w Programowaniu Indywidualnym

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.