Cykl nieparzysty

Limit pamięci: 64 MB

Mając dany graf nieskierowany, znajdź w nim cykl nieparzystej długości.

Zadanie

Wczytaj liczbę oznaczającą liczbę przypadków testowych oraz opisów grafów. Dla każdego z grafów należy stwierdzić, czy istnieje w nim cykl nieparzystej długości.

Wejście

Pierwszy wiersz wejścia zawiera liczbę (). Dalej następuje opisów grafów nieskierowanych. Opis takiego grafu zawiera na początku dwie liczby i oznaczające odpowiednio liczbę wierzchołków i liczbę krawędzi (, ). Kolejne wierszy zawiera opis krawędzi. W każdym z tych wierszy znajdują się dwie liczby całkowite ze zbioru reprezentujące końce jednej krawędzi.

Wyjście

Dla każdego grafu z wejścia należy wypisać dokładnie jeden wiersz z odpowiedzią. Jeśli jest cykl, należy wypisać słowo TAK i po spacji kolejne wierzchołki cyklu. Wystarczy wypisać dowolny cykl, przy czym wierzchołki nie mogą się powtarzać. Jeśli cyklu nie ma, należy wypisać NIE.

Przykład

Dla danych wejściowych:

2
4 6
1 2
1 3
1 4
2 3
2 4
3 4
4 4
1 2
2 3
3 4
4 1

poprawną odpowiedzią jest:

TAK 2 1 3
NIE

Autor zadania: Wojciech Śmietanka.