시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB3000.000%

문제

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

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

입력

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

출력

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.

예제 입력 1

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

예제 출력 1

TAK 2 1 3
NIE

출처

Camp > POI Training Camp > ONTAK 2009 1-2번