Osadzenie grafu w przestrzeni polega na umieszczeniu każdego wierzchołka w innym punkcie oraz narysowaniu każdej krawędzi jako prostego łuku łączącego jej dwa wierzchołki, tak aby żadne dwa łuki nie przecinały się poza wspólnym wierzchołkiem. W tym zadaniu rozważamy osadzenia w przestrzeni trójwymiarowej spełniające pewne warunki.

Dany jest prosty graf nieskierowany o $n$ wierzchołkach i $m$ krawędziach, czyli każdą parę wierzchołków łączy co najwyżej jedna krawędź, a każda krawędź łączy różne wierzchołki. Wierzchołki są ponumerowane od $1$ do $n$, a krawędzie od $1$ do $m$. Krawędź $j$ łączy różne wierzchołki $v_j$ i $w_j$. Każdy wierzchołek jest incydentny z co najwyżej pięcioma krawędziami.

Znajdź osadzenie grafu spełniające wszystkie poniższe warunki.

• Każdy wierzchołek $i$ jest osadzony jako punkt $(x_i,y_i,0)$. Współrzędne $x_i,y_i$ muszą być liczbami całkowitymi od $0$ do $400$ włącznie. Wszystkie punkty muszą mieć różne współrzędne.

• Każda krawędź $j$ jest osadzona jako łamana (połączony ciąg odcinków) o końcach w punktach osadzenia wierzchołków $v_j,w_j$. Każdy odcinek musi być równoległy do osi $x$, $y$ lub $z$. Każdy punkt łamanej musi mieć całkowite współrzędne od $0$ do $400$ włącznie. Każda łamana może mieć co najwyżej $30$ punktów, licząc końce.

• Łamane nie mogą przecinać samych siebie. Różne łamane nie mogą dzielić żadnego punktu, chyba że odpowiadają krawędziom incydentnym z tym samym wierzchołkiem. W takim przypadku mogą dzielić tylko ten jeden koniec.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $n,m$ ($2\le n\le1600$, $1\le m\le4000$). W $j$-tym z kolejnych $m$ wierszy są dwie liczby całkowite $v_j,w_j$ ($1\le v_j<w_j\le n$).

Wejście gwarantuje, że każdy wierzchołek jest incydentny z co najwyżej pięcioma krawędziami. Nie ma też krawędzi równoległych: jeśli $j\ne j^{\prime}$, zachodzi $(v_j,w_j)\ne(v_{j^{\prime}},w_{j^{\prime}})$.

Wyjście

Najpierw wypisz $n$ wierszy. W $i$-tym podaj dwie liczby całkowite $x_i,y_i$, określające pozycję osadzenia wierzchołka $i$. Następnie wypisz $m$ wierszy, gdzie $j$-ty reprezentuje łamaną odpowiadającą krawędzi $j$ w następującym formacie:

$$k\ x^{\prime}_1\ y^{\prime}_1\ z^{\prime}_1\ \cdots\ x^{\prime}_k\ y^{\prime}_k\ z^{\prime}_k$$

Tutaj $k$ oznacza liczbę punktów i musi być od $2$ do $30$ włącznie. Punkty $(x^{\prime}_1,y^{\prime}_1,z^{\prime}_1),\ldots,(x^{\prime}_k,y^{\prime}_k,z^{\prime}_k)$ są punktami łamanej. Pierwszy punkt $(x^{\prime}_1,y^{\prime}_1,z^{\prime}_1)$ musi być równy $(x_{v_j},y_{v_j},0)$, a ostatni $(x^{\prime}_k,y^{\prime}_k,z^{\prime}_k)$ musi być równy $(x_{w_j},y_{w_j},0)$. Każdą parę kolejnych punktów łączy odcinek tworzący łamaną. Każdy odcinek musi mieć dodatnią długość. Dwa kolejne odcinki mogą mieć tę samą orientację, na przykład oba być równoległe do osi $x$.

Wypisane osadzenie musi spełniać wszystkie warunki wymienione powyżej.

Przy podanych ograniczeniach wejścia można wykazać, że istnieje przynajmniej jedno poprawne wyjście. Jeśli istnieje wiele rozwiązań, każde z nich zostanie zaakceptowane.

Uwagi

Uwagi dotyczące specjalnego sprawdzania:

Otrzymujesz narzędzie wiersza poleceń do lokalnych testów. Plik można pobrać z DOMjudge. Na początku narzędzia znajdują się komentarze wyjaśniające jego użycie.

Przykład

Wejście 1

3 3
1 2
1 3
2 3

Wyjście 1

0 0
400 0
0 399
3 0 0 0 100 0 0 400 0 0
4 0 0 0 0 0 200 0 399 200 0 399 0
3 400 0 0 400 399 0 0 399 0

Uwagi

Objaśnienie przykładowego wejścia/wyjścia 1

Rysunek B.1 przedstawia osadzenie reprezentowane przez przykładowe wyjście.

Rysunek B.1: ilustracja osadzenia.