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

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.

예제 입력

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

예제 출력

TAK 2 1 3
NIE