시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 3 | 0 | 0 | 0.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
.
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
Camp > POI Training Camp > ONTAK 2009 1-2번