说明

图在空间中的嵌入是一种将每个顶点放置于空间中不同点，并将每条边绘制为连接其两个顶点的简单弧线的方式，使得除共享顶点外没有两条弧线相交。在本问题中，我们关注在特定条件下三维空间中的嵌入。

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

找到该图的一个嵌入，满足以下所有条件。

• 每个顶点 $i$ 嵌入为空间中的点 $(x_i, y_i, 0)$。坐标 $x_i$ 和 $y_i$ 必须是介于 $0$ 到 $400$（包含）的整数。所有点必须有互不相同的坐标。
• 每条边 $j$ 嵌入为一条折线（一系列相连的线段），以其两个端点对应顶点 $v_j$ 和 $w_j$ 的嵌入点作为端点。折线的每一段必须平行于 $x$ 轴、$y$ 轴或 $z$ 轴。折线的每个节点坐标必须为介于 $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 \ \cdots \ x'_k \ y'_k \ z'_k$$

这里 $k$ 是节点数量，必须介于 $2$ 和 $30$ 之间（包含）。点 $(x'_1, y'_1, z'_1), \ldots, (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 下载该文件。该工具顶部有注释说明其用法。

3 3
1 2
1 3
2 3

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 展示了样例输出所代表的嵌入。

:::align{center} :::

翻译由 DeepSeek 完成