Una inmersión de un grafo en un espacio consiste en situar cada vértice en un punto distinto del espacio y dibujar cada arista como un arco simple que conecta sus dos vértices, de modo que dos arcos no se intersequen salvo en un vértice compartido. En este problema nos centramos en inmersiones en un espacio tridimensional bajo ciertas condiciones.

Se te da un grafo simple no dirigido con $n$ vértices y $m$ aristas: hay como máximo una arista entre cualquier par de vértices y cada arista conecta vértices diferentes. Los vértices están numerados del $1$ al $n$ y las aristas del $1$ al $m$. La arista $j$ conecta dos vértices distintos $v_j,w_j$. Cada vértice es incidente con como máximo cinco aristas.

Encuentra una inmersión del grafo que cumpla todas las siguientes condiciones.

• Cada vértice $i$ se sitúa en el punto $(x_i,y_i,0)$ del espacio. Las coordenadas $x_i,y_i$ deben ser enteros entre $0$ y $400$, ambos incluidos. Todos los puntos deben tener coordenadas diferentes.

• Cada arista $j$ se representa por una polilínea (una serie conectada de segmentos) con los puntos de los vértices $v_j,w_j$ como extremos. Cada segmento debe ser paralelo al eje $x$, $y$ o $z$. Cada nodo de la polilínea debe tener coordenadas enteras entre $0$ y $400$, ambos incluidos. Cada polilínea debe tener como máximo $30$ nodos, contando sus extremos.

• Las polilíneas no deben intersecarse a sí mismas. Dos polilíneas distintas no deben compartir ningún punto, salvo cuando corresponden a aristas incidentes con el mismo vértice. En ese caso solo pueden compartir ese único extremo.

Entrada

La primera línea de entrada contiene dos enteros $n,m$ ($2\le n\le1600$, $1\le m\le4000$). La línea $j$ de las siguientes $m$ líneas contiene dos enteros $v_j,w_j$ ($1\le v_j<w_j\le n$).

Se garantiza que cada vértice es incidente con como máximo cinco aristas. Además, no hay aristas paralelas: si $j\ne j^{\prime}$, se cumple $(v_j,w_j)\ne(v_{j^{\prime}},w_{j^{\prime}})$.

Salida

Primero escribe $n$ líneas. La línea $i$ debe contener dos enteros $x_i,y_i$ que representan las coordenadas donde se sitúa el vértice $i$. Después escribe $m$ líneas, donde la línea $j$ representa la polilínea de la arista $j$ con el siguiente formato:

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

Aquí, $k$ es el número de nodos y debe estar entre $2$ y $30$, ambos incluidos. Los puntos $(x^{\prime}_1,y^{\prime}_1,z^{\prime}_1),\ldots,(x^{\prime}_k,y^{\prime}_k,z^{\prime}_k)$ son los nodos de la polilínea. El primer punto $(x^{\prime}_1,y^{\prime}_1,z^{\prime}_1)$ debe ser $(x_{v_j},y_{v_j},0)$ y el último $(x^{\prime}_k,y^{\prime}_k,z^{\prime}_k)$ debe ser $(x_{w_j},y_{w_j},0)$. Cada par de puntos consecutivos se conecta mediante un segmento para formar la polilínea. Cada segmento debe tener longitud positiva. Dos segmentos consecutivos pueden tener la misma orientación; por ejemplo, ambos pueden ser paralelos al eje $x$.

La inmersión que escribas debe cumplir todas las condiciones anteriores.

Bajo las restricciones de entrada dadas, se puede demostrar que existe al menos una salida válida. Si hay varias, se aceptará cualquiera de ellas.

Nota

Notas sobre la evaluación especial:

Se proporciona una herramienta de línea de comandos para pruebas locales. Puedes descargar el archivo desde DOMjudge. Al principio de la herramienta hay comentarios que explican cómo usarla.

Ejemplos

Entrada 1

3 3
1 2
1 3
2 3

Salida 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

Nota

Explicación de la entrada/salida de ejemplo 1

La figura B.1 ilustra la inmersión representada por la salida de ejemplo.

Figura B.1: ilustración de la inmersión.