10013번 - Graf planarny 다국어

Dany jest dwuspójny wierzchołkowo¹ graf³ planarny⁵ G. W tym grafie co najwyżej dwie ściany⁷ 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⁸ parzystej długości.

¹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².

²Graf spójny jest to taki graf G = (V, E), że dla każdego podziału na niepuste podzbiory V₁, V₂ ⊆ V, V₁ ∩ V₂ = ∅, V₁ ∪ V₂ = V istnieje krawędź uv ∈ E, taka że u ∈ V₁ oraz v ∈ V₂.

³Grafem nazywamy parę (V, E), gdzie E jest multizbiorem⁴ dwuelementowych podzbiorów V.

⁴Multizbiór to zbiór, w którym elementy mogą się powtarzać; formalnie, jest to funkcja z dowolnego zbioru w zbiór liczb naturalnych.

⁵Graf G = (V, E) nazywamy planarnym, gdy istnieje planarne włożenie⁶ tego grafu w płaszczyznę.

⁶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.

⁷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.

⁸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.

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.

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.