POLSKI SPOJ

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 a_i b_i, które oznaczają, że polanki o numerach a_i oraz b_i są połączone alejką (1<=a_i,b_i<=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