Spoty informatyczne

Kaktus

Prędzej mi kaktus na dłoni wyrośnie, niż podejmę się takiego zadania! - zawołał Witek. Chłopcy zajęli się analizą grafów (nieskierowanych). Witkowi w przypadł w udziale obowiązek liczenia, ile różnych cykli (prostych, czyli bez powtarzających się wierzchołków) znajduje się w zadanym grafie. Witek uważa to zadanie za zdecydowanie zbyt pracochłonne i stąd jego okrzyk protestu. Po pewnym czasie chłopcom udało się dojść do porozumienia - zadanie Witka pozostanie wprawdzie niezmienione, ale chłopcy ograniczą się do badania grafów, w których policzyć cykle powinno być stosunkowo łatwo, a dokładniej do takich grafów, w których dowolne dwa różne cykle mają co najwyżej jeden wspólny wierzchołek. Pomóż Witkowi w wykonywaniu jego pracy. Jeżeli okaże się, że zadany graf nie spełnia założenia, odmów wykonania zadania.

Wejście
W pierwszej linii znajduje się jedna liczba naturalna L, oznaczająca liczbę zestawów danych. Potem następuje opis kolejnych zestawów. W pierwszej linii opisu znajdują się dwie liczby naturalne N i M (1<= N, M <= 1000000), oznaczające - odpowiednio - liczbę wierzchołków i liczbę krawędzi grafu. Następnie podawany jest opis krawędzi grafu w M kolejnych liniach. Każda z nich zawiera dwie różne liczby naturalne A i B oznaczające wierzchołki, które łączy dana krawędź (numerowane od 0). Krawędzie są parami różne.

Wyjście
Dla każdego zestawu w osobnej linii należy wypisać liczbę cykli w grafie, jeśli ten spełnia opisane w treści założenie, lub quot;NIE" w przeciwnym wypadku.

Puzzle

Po skończeniu codziennego grabienia liści, pan Wincenty postanowił zrelaksować się przy swojej ulubionej rozrywce - układaniu puzzli. Znalazł w szafce biurka stary zestaw i zabrał się do układania. Po chwili wiedział już, który kawałek pasuje do którego oraz znał pierwsze dwa elementy pierwszego rzędu puzzli. Znał też oczywiście rozmiary obrazka. Czy ta wiedza wystarczy do jednoznacznego odtworzenia całej układanki?

Wejście
W pierwszej linii znajdują się dwie liczby naturalne N i M  (3 <= N <= M, N*M <= 1000), N oznacza liczbę wierszy, a M - liczbę kolumn układanki. Następnie w kolejnych N*M liniach znajdują się opisy kolejnych kawałków układanki (od kawałka nr 1 do kawałka nr N*M). Każdy opis składa się dokładnie z czterech liczb całkowitych, nieujemnych - numerów kawałków, do których dany kawałek pasuje. Jeśli dany element leży na brzegu obrazka, to zamiast numeru odpowiedniego sąsiada podawana jest liczba 0. W ostatniej linii znajdują się dwie liczby naturalne A i B - numery, kolejno, dwóch pierwszych elementów pierwszego rzędu układanki.

Wyjście
Na wyjściu należy wpisać "NIE", w przypadku gdy dla podanych danych nie da się jednoznacznie określić rozwiązania układanki. W przeciwnym przypadku należy wypisać ułożoną układankę, w N kolejnych liniach, z których każda ma zawierać oddzielone spacjami M numerów kolejnych elementów w danym rzędzie.