图在空间中的嵌入是指将每个顶点放置在空间中的不同点上，并将每条边绘制为连接其两个顶点的简单弧线，使得除公共顶点外，任意两条弧线均不相交。在本题中，我们关注在特定条件下三维空间中的嵌入。

给定一个具有 $n$ 个顶点和 $m$ 条边的简单无向图，这意味着任意一对顶点之间最多只有一条边，且每条边连接不同的顶点。顶点编号从 1 到 $n$，边编号从 1 到 $m$。第 $j$ 条边连接两个不同的顶点 $v_j$ 和 $w_j$。每个顶点关联的边数不超过五条。

请找到该图的一种嵌入方式，使得满足以下所有条件：

• 每个顶点 $i$ 被嵌入为空间中的点 $(x_i, y_i, 0)$。坐标 $x_i$ 和 $y_i$ 必须是 0 到 400 之间的整数（包含 0 和 400）。所有点必须具有不同的坐标。
• 每条边 $j$ 被嵌入为一条折线（一系列相连的线段），其端点为顶点 $v_j$ 和 $w_j$ 的嵌入点。折线的每一段必须平行于 $x$ 轴、$y$ 轴或 $z$ 轴。折线的每个节点必须具有 0 到 400 之间的整数坐标（包含 0 和 400）。每条折线的节点数（包括端点）不得超过 30 个。
• 折线不得自交。不同的折线不得共享任何点，除非它们对应于关联同一个顶点的边。在这种情况下，它们只能共享该公共端点。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 1600$, $1 \le m \le 4000$)。接下来的 $m$ 行中，第 $j$ 行包含两个整数 $v_j$ 和 $w_j$ ($1 \le v_j < w_j \le n$)。

输入保证每个顶点关联的边数不超过五条。此外，不存在平行边；即若 $j \neq j'$，则 $(v_j, w_j) \neq (v_{j'}, w_{j'})$ 成立。

输出格式

首先，输出 $n$ 行。第 $i$ 行应包含两个整数 $x_i$ 和 $y_i$，表示顶点 $i$ 嵌入的坐标。然后，输出 $m$ 行，其中第 $j$ 行表示对应于边 $j$ 的折线，格式如下：

$k \ x_1 \ y_1 \ z_1 \ \dots \ x_k \ y_k \ z_k$

其中 $k$ 是节点数，必须在 2 到 30 之间（包含 2 和 30）。点 $(x_1, y_1, z_1), \dots, (x_k, y_k, z_k)$ 是折线的节点。第一个点 $(x_1, y_1, z_1)$ 必须是 $(x_{v_j}, y_{v_j}, 0)$，最后一个点 $(x_k, y_k, z_k)$ 必须是 $(x_{w_j}, y_{w_j}, 0)$。每对连续的点通过一段线段连接以形成折线。每段线段的长度必须为正。两条连续的线段可以具有相同的方向；例如，它们都可以平行于 $x$ 轴。

你输出的嵌入必须满足上述所有条件。

在给定的输入约束下，可以证明至少存在一个有效的输出。如果存在多个输出，接受其中任何一个即可。

说明

你可以在 DOMjudge 上下载一个用于本地测试的命令行工具。该工具的顶部包含解释其用法的注释。

样例

样例输入 1

3 3
1 2
1 3
2 3

样例输出 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

样例说明 1

图 B.1 展示了样例输出所表示的嵌入。

图 B.1：嵌入示意图。