Dany jest dwuspójny wierzchołkowo^{1} graf^{3} planarny^{5} $ G $. W tym grafie co najwyżej dwie ściany^{7} są otoczone nieparzystą liczbą krawędzi. Dane jest również planarne włożenie grafu $ G $ w płaszczyznę. Należy sprawdzić, czy istnieje podział krawędzi $ G $ na pewną liczbę cykli prostych^{8} parzystej długości.
^{1}Graf dwuspójny wierzchołkowo jest to taki graf $ G $ = ($ V $, $ E $), że dla każdego $ v $ ∈ $ V $, graf ($ V $ \ {$ v $}, $ E $) jest spójny^{2}.
^{2}Graf spójny jest to taki graf $ G $ = ($ V $, $ E $), że dla każdego podziału na niepuste podzbiory $ V $_{1}, $ V $_{2} ⊆ $ V $, $ V $_{1} ∩ $ V $_{2} = ∅, $ V $_{1} ∪ $ V $_{2} = $ V $ istnieje krawędź $ uv $ ∈ $ E $, taka że $ u $ ∈ $ V $_{1} oraz $ v $ ∈ $ V $_{2}.
^{3}Grafem nazywamy parę ($ V $, $ E $), gdzie $ E $ jest multizbiorem^{4} dwuelementowych podzbiorów $ V $.
^{4}Multizbiór to zbiór, w którym elementy mogą się powtarzać; formalnie, jest to funkcja z dowolnego zbioru w zbiór liczb naturalnych.
^{5}Graf $ G $ = ($ V $, $ E $) nazywamy planarnym, gdy istnieje planarne włożenie^{6} tego grafu w płaszczyznę.
^{6}Planarne włożenie grafu planarnego w płaszczyznę to taki rysunek grafu, na którym każdemu wierzchołkowi przyporządkowany jest inny punkt płaszczyzny, natomiast każdej krawędzi - krzywa łącząca punkty przyporządkowane wierzchołkom połączonym przez tę krawędź. Każda krzywa może przecinać się z innym wierzchołkiem lub krzywą jedynie w swoim końcu.
^{7}Rozważmy planarne włożenie grafu planarnego w płaszczyznę. Ścianą grafu nazywamy każdy z obszarów płaszczyzny ograniczony krzywymi odpowiadającymi krawędziom. Zwróć uwagę, że w każdym grafie istnieje również nieskończona ściana "otaczająca" graf.
^{8}Zbiór krawędzi $ C $ ⊆ $ E $ nazywamy cyklem prostym, gdy krawędzie te tworzą graf spójny, w którym każdy wierzchołek jest incydentny z dokładnie dwiema krawędziami.
Input Format
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $ n $ i $ m $ (2 ≤ $ n $ ≤ 1 000 000, 1 ≤ $ m $ ≤ 5 000 000). Liczba $ n $ oznacza liczbę wierzchołków, zaś $ m $ - liczbę krawędzi w grafie $ G $. Wierzchołki są ponumerowane liczbami od 1 do $ n $, zaś krawędzie - liczbami od 1 do $ m $. Każda z krawędzi łączy dwa różne wierzchołki. Pomiędzy daną parą wierzchołków może istnieć wiele krawędzi.
Dalej następuje $ n $ wierszy opisujących krawędzie grafu; $ i $-ty z tych wierszy zawiera opis krawędzi incydentnych z wierzchołkiem $ i $. Opis ten rozpoczyna się liczbą całkowitą $ s_{i} $ (1 ≤ $ s_{i} $ ≤ $ m $), po której następuje lista $ s_{i} $ liczb całkowitych z zakresu od 1 do $ m $. Każda z tych liczb oznacza numer jednej krawędzi incydentnej z wierzchołkiem $ i $. Lista zawiera krawędzie uporządkowane kolejno wokół wierzchołka $ i $, w porządku zgodnym z kierunkiem ruchu wskazówek zegara.
Output Format
Jeśli odpowiedni podział krawędzi nie istnieje, to w jedynym wierszu wyjścia należy wypisać słowo NIE.
W przeciwnym razie, w pierwszym wierszu wyjścia należy wypisać słowo TAK. W kolejnych wierszach należy wypisać poprawny podział krawędzi grafu $ G $ na cykle proste. Każdy z tych wierszy powinien rozpoczynać się liczbą całkowitą $ j $ (2 ≤ $ j $ ≤ $ n $). Po niej wypisać należy $ j $ numerów krawędzi tworzących opisywany cykl prosty. Każde dwie kolejne krawędzie powinny mieć wspólny wierzchołek. Każda krawędź powinna zostać wypisana na wyjściu dokładnie raz.
Example
Input
10 16 2 1 8 2 8 7 4 1 9 2 14 4 6 13 7 14 4 16 10 9 15 4 16 15 13 12 4 2 10 3 11 4 5 12 6 11 2 3 4 2 4 5
Output
TAK 6 16 10 3 4 5 12 4 6 11 2 14 6 8 1 9 15 13 7