Piękno wg elfów

Jeśli już zrobiłeś to zadanie, polecamy zadanie ciut trudniejsze: Większe piękno wg elfów.

Elfy uznają tylko jeden sposób rysowania grafów.

Załóżmy, że mamy dany graf o n wierzchołkach. Rysujemy oś liczbową i umieszczamy wierzchołki w punktach 1, 2, 3, ..., n, po czym rysujemy wszystkie krawędzie grafu. Graf jest narysowany pięknie, jeśli żadna krawędź nie łączy wierzchołków, które są w odległości większej niż 3, tj numery tych wierzchołków różnią się o więcej niż o trzy.

Elfy zapewne nie zauważyły, że nie każdy graf da się pięknie narysować. Napisz program, który określa, czy graf da się pięknie narysować.

Możesz założyć, że wszystkie grafy w testach są spójne.

Wejście, wyjście

W pierwszej linii wejścia jest liczba grafów do rozpoznania d, d <= 10. Dalej następuje opis d grafów.

Opis w pierwszej linii ma dwie liczby całkowite 2 <= n <= 13, i 0 <= m <= 78, oznaczające liczbę wierzchołków i krawędzi w grafie. Kolejne m wierszy to opisy krawędzi: w takim wierzu są dwa różne numery wierzchołków 1 <= a, b <= n, krawędź łączy wierzchołki a i b.

Dla każdego grafu z wejścia wypisz w osobnej linii TAK lub NIE, w zależności od tego, czy ten graf da się pięknie narysować czy nie.

Przykład

Dla danych:

2
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
5 5
1 2
2 3
3 4
4 5
5 1

poprawną odpowiedzią jest:

NIE
TAK

Pierwszy graf to klika 5-wierzchołkowa. Jakkolwiek elfy by jej nie rysowały, będzie krawędź łącząca wierzchołek umieszczony w jedynce i w piątce.

Drugi graf to cykl 5-wierzchołkowy. Można go narysować tak: 

 /---\ /---\
*  *  *  *  *
 \/ \---/ \/