Problem description

Jak wszyscy wiemy, w Minecrafcie istnieją wioski. Steve bardzo lubi odwiedzać swoich znajomych wieśniaków, dlatego pomiędzy niektórymi parami wiosek zbuduje bezpośrednie połączenia kolejowe. Żadne dwa tory nie będą się krzyżować, ponieważ tam, gdzie jest to konieczne, powstaną tunele lub estakady. Innymi słowy, wioski wraz z połączeniami kolejowymi będą tworzyły graf.

Jedyną rzeczą, która cieszy Steve’a bardziej niż zdobywanie diamentów, jest widok kotów. Dlatego chce on, aby w każdej wiosce znajdowała się ich pewna liczba, przy czym muszą być spełnione następujące warunki:

1. Nie istnieje cykl wiosek taki, że w każdej wiosce na tym cyklu znajduje się taka sama liczba kotów.

2. Dla każdej pary różnych liczb kotów c_i, c_j występujących w pewnych wioskach, istnieje cykl, na którym:

   • znajduje się co najmniej jedna wioska z liczbą kotów c_i
   • znajduje się co najmniej jedna wioska z liczbą kotów c_j
   • nie znajduje się żadna wioska z inną liczbą kotów.

Cyklem nazywamy ciąg różnych wiosek (W₁,…,W_c) (3≤c) taki, że istnieje bezpośrednie połączenie kolejowe pomiędzy wioskami W_i i W_i + 1 dla każdego 1 ≤ i ≤ c − 1 oraz pomiędzy wioskami W_c i W₁.

Steve nie jest jednak pewny, jak dokładnie będzie wyglądała sieć kolejowa, ani nawet ile wiosek będzie chciał w niej uwzględnić. Pomóż mu stwierdzić dla każdego planu, ile kotów powinno znajdować się w każdej wiosce, lub określić, że spełnienie jego wymagań nie jest możliwe.

Wejście

W pierwszym wierszu wejścia znajduje się liczba T oznaczająca liczbę planów sieci kolejowych.

W pierwszym wierszu opisu każdego planu znajdują się dwie liczby naturalne N oraz M, określające odpowiednio liczbę wiosek i połączeń kolejowych. W kolejnych M wierszach podane są dwie liczby naturalne A_i oraz B_i, oznaczające, że pomiędzy wioskami A_i oraz B_i istnieje bezpośrednie połączenie kolejowe.

Gwarantowane jest, że A_i ≠ B_i. Każda nieuporządkowana para (A_i,B_i) może wystąpić w planie co najwyżej raz.

Wyjście

Dla każdego planu, jeżeli nie istnieje poprawne przyporządkowanie liczby kotów, wypisz pojedynczy wiersz zawierający słowo NIE. W przeciwnym wypadku wypisz wiersz ze słowem TAK oraz liczbę naturalną K, oznaczającą maksymalną liczbę kotów w pewnej wiosce. W następnym wierszu wypisz N liczb naturalnych z zakresu od 1 do K, gdzie i-ta liczba oznacza liczbę kotów w wiosce i, tak aby warunki Steve’a były spełnione oraz aby dla każdego 1 ≤ x ≤ K istniała co najmniej jedna wioska z dokładnie x kotami.

Jeżeli istnieje wiele poprawnych rozwiązań, wypisz dowolne z nich.

Ograniczenia

1 ≤ T ≤ 2 000, 2 ≤ N ≤ 1 000 000, 1 ≤ M ≤ 3 000 000, 1 ≤ A_i, B_i ≤ N. Suma N + M po wszystkich planach wynosi co najwyżej 4 000 000.

Podzadania

Przykład

2
5 8
1 2
1 3
1 4
2 3
5 1
4 3
4 5
5 2
4 2
1 2
3 4

TAK 2
1 1 2 1 2
TAK 1
1 1 1 1