Problem description

O nie! Koniec jest już blisko! Najlepsi światowi astronomowie właśnie odkryli ogromny meteoryt, który zmierza dokładnie w kierunku słońca! W momencie gdy dojdzie do zderzenia, wszystkie planety w całym układzie planetarnym ulegną zniszczeniu. Jedyną nadzieją jest teleportacja ludności na inny zbiór planet, którym zagłada nie grozi.

Sztab kryzysowy rozpoczął już działania w tym kierunku. Z racji, że podczas zderzenia N starych planet ulegnie zniszczeniu, zostało już wybrane inne N nowych planet, na które zostaną przetransportowani mieszkańcy. Będzie się to działo poprzez specjalny system teleportów, z których każdy będzie miał możliwość przeniesienia dowolnej liczby osób z pewnej starej planety na pewną nową planetę.

Plan sieci teleportów musi zapewniać komfort teleportowanym mieszkańcom. Z tego względu system teleportów będzie musiał spełniać kryterium, że dla każdego zbioru pewnych k starych planet, ich teleporty będą prowadzić do co najmniej k różnych nowych planet. Tylko takie plany będą uznawane za dopuszczalne, gdyż plany przenosin nie spełniające tego kryterium mogą spowodować, że mieszkańcom będzie za ciasno.

Jednakże są też grupy mieszkańców, które nie powinny się nadmiernie rozprzestrzenić, dlatego niektóre zbiory starych planet powinny być ograniczone. Oznacza to, że dla pewnych zbiorów k starych planet, ich teleporty powinny prowadzić do dokładnie k różnych nowych planet.

Sztab kryzysowy zlecił już pewnemu studentowi przygotowanie układu teleportów. Jednakże, jak się można było domyślić, plan ten nie dość, że niekoniecznie jest optymalny pod względem ilości teleportów, to jeszcze nie wiadomo czy jest dopuszczalny! Dlatego teraz sztab zwrócił się o pomoc do kogoś bardziej doświadczonego, czyli właśnie do Ciebie.

Twoim zadaniem jest teraz weryfikacja oraz optymalizacja tego planu. Jeżeli dostarczony Tobie plan nie jest dopuszczalny, powinieneś udowodnić to Sztabowi, wskazując zbiór planet, który nie spełnia tego kryterium. W sytuacji, gdy jednak plan jest dopuszczalny, Twoim zadaniem jest wskazanie dopuszczalnego planu, który minimalizuje liczbę teleportów. Powinien on spełniać kryterium, że jeśli jakiś zbiór planet był wcześniej ograniczony, to w nowym planie też powinien być on ograniczony. Analogicznie, jeśli zbiór planet nie był ograniczony, to w nowym planie też nie powinien być.

Czy podołasz temu arcytrudnemu zadaniu? Teraz zależą od Ciebie losy nie tylko świata, ale i całego układu planetarnego!

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N oraz M, oddzielone pojedynczym odstępem. Liczba N oznacza zarówno liczbę starych, jak i nowych planet. Liczba M oznacza liczbę teleportów w pierwotnym planie teleportacji.
W kolejnych M wierszach podane są opisy kolejnych teleportów. Każdy z nich zawiera dwie liczby całkowite x oraz y, oddzielone pojedynczym odstępem, oznaczające, że na starej planecie o numerze x zaplanowany jest teleport na nową planetę y. Każda para x, y może wystąpić na wejściu co najwyżej raz. Stare planety są numerowane liczbami od 1 do N, a nowe numerami od N + 1 do 2 ⋅ N.

Wyjście

Jeżeli plan teleportacji podany na wejściu nie jest dopuszczalny, w pierwszym wierszu wyjścia wypisz jedno słowo NIE. W drugim wierszu wyjścia wypisz liczbę k, a w trzecim wierszu wypisz k liczb x₁, x₂, …, x_k, oddzielonych pojedynczymi odstępami. Liczby te powinny oznaczać, że w pierwotnym planie teleportacji ze zbioru starych planet S = {x₁, x₂, …, x_k} nie da się teleportować do k różnych nowych planet.
Jeżeli jednak podany na wejściu plan teleportacji jest dopuszczalny, w pierwszym wierszu wyjścia wypisz jedno słowo TAK. W drugim wierszu wyjścia wypisz liczbę M′, oznaczającą liczbę teleportów w nowym, również dopuszczalnym planie teleportacji. Następnie, w kolejnych M′ wierszach wypisz kolejne teleporty z nowego planu, w takim samym formacie jak na wejściu.

Ograniczenia

1 ≤ N ≤ 1000, 0 ≤ M ≤ N², dla każdego zaplanowanego teleportu zachodzi 1 ≤ x ≤ N, N + 1 ≤ y ≤ 2 ⋅ N.

Przykłady

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

TAK
6
1 4
1 5
2 5
2 6
3 6
3 4

3 4
1 4
1 5
2 6
3 6

NIE
2
2 3 

3 6
1 4
1 5
2 4
2 5
1 6
3 6

TAK
6
3 6
1 4
1 5
2 5
2 4
1 6