Contest problemset 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

Jednym z podstawowych elementów przetrwania w grze Minecraft jest unikanie głodu. Alex odczuwa głód, dlatego postanowiła złowić ryby w pobliskim jeziorze. W rejonie jeziora, w którym się znajduje, ryb jest jednak niewiele, dlatego postanowiła przepłynąć na jego przeciwległy róg i spróbować łowić tam.

Jezioro ma kształt prostokąta o wymiarach N × M bloków. Początkowo łódka Alex znajduje się w bloku położonym w rogu jeziora o współrzędnych (1,1), a celem jest dopłynięcie do przeciwległego rogu jeziora, czyli bloku o współrzędnych (N,M). Alex może poruszać się wyłącznie w górę, w dół oraz na boki i nie może opuszczać łódki. Jezioro znajduje się w biomie tajgi, w związku z czym część jego bloków stanowią bloki lodu, przez które łódka nie może przepłynąć, a pozostałe bloki są blokami wody.

Alex ma zużyty kilof, za pomocą którego może niszczyć bloki lodu, torując sobie drogę. Kilof jest niemal całkowicie wyczerpany, dlatego Alex może zniszczyć jedynie 2 bloki lodu. Ponadto, z powodu ograniczonego miejsca w ekwipunku, postanowiła zniszczyć dokładnie 2 bloki lodu, żeby w pełni zużyć kilof.

Alex zastanawia się, na ile różnych sposobów może to osiągnąć. Pomóż jej i wyznacz liczbę par bloków lodu, znajdujących się w dowolnym miejscu w obszarze jeziora, po których zniszczeniu Alex będzie mogła przepłynąć przez jezioro.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i M, oznaczające wymiary jeziora.

Następne N wierszy opisuje jezioro, każdy wiersz zawiera M znaków . lub X, j-ty znak w i-tym wierszu (B_i, j) określa, czy blok o współrzędnych (i,j) jest blokiem wody (B_i, j= .) czy blokiem lodu (B_i, j= X).

Jest gwarantowane, że B_1, 1 = B_N, M= .

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna znaleźć się pojedyncza liczba całkowita oznaczająca liczbę różnych par bloków lodu, po których zniszczeniu Alex może przepłynąć z (1,1) do (N,M).

Ograniczenia

1 ≤ N ⋅ M ≤ 250 000, 1 ≤ N, M

Podzadania

Przykłady

3 5
..X..
.XX..
..XX.

7

3 2
..
X.
..

0

5 7
.....X.
.XX.XX.
X..X.X.
.XX.XX.
.....X.

17