骨架数据已广泛应用于动作识别等计算机视觉任务中。在骨架模型中，人体由一组通过骨骼连接的身体关节表示。这自然形成了一个无向图模型：顶点是关节，边是骨骼。

为了整合视频中骨架的动态变化，我们可以跟踪各帧中的关节，并为视频构建一个时空图。时空图由每一帧的骨架图组成，并带有连接相邻两帧中相同关节的额外帧间边。注意，视频中所有帧的骨架图应保持一致。下图展示了时空图是如何形成的。

图 4：时空图的形成

你的任务是逆向工程一个时空图。形式上，你需要为图中的每个顶点 $v$ 分配一对整数 $(f_v, s_v)$，其中 $f_v$ 是帧编号，$s_v$ 是关节索引。设 $T$ 和 $S$ 分别表示帧数和关节数，则你的标注必须同时满足以下条件：

• 对于每个 $1 \le t \le T$ 和 $1 \le i \le S$，恰好有一个顶点被标注为 $(t, i)$；
• 对于每个 $1 \le t < T$ 和 $1 \le i \le S$，标注为 $(t, i)$ 和 $(t + 1, i)$ 的顶点之间存在一条边；除此之外不存在其他帧间边；
• 对于每个 $1 \le t_1 < t_2 \le T$ 和 $1 \le i < j \le S$，标注为 $(t_1, i)$ 和 $(t_1, j)$ 的顶点之间存在边，当且仅当标注为 $(t_2, i)$ 和 $(t_2, j)$ 的顶点之间也存在边。

输入格式

输入的第一行包含两个整数 $n, m$ ($1 \le n \le 100\,000, 0 \le m \le 200\,000$)，分别表示给定时空图的顶点数和边数。图的顶点索引为 $1$ 到 $n$。

接下来的 $m$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n, u \neq v$)，表示连接索引为 $u$ 和 $v$ 的顶点的无向边。每对顶点之间最多只有一条边。保证输入图是连通的。

输出格式

在输出的第一行打印两个整数 $T$ 和 $S$，分别表示帧数和关节数。然后打印 $T$ 行，每行包含 $S$ 个整数；第 $t$ 行的第 $s$ 个整数是标注为 $(t, s)$ 的顶点的索引。

如果存在多种有效的标注方式，请打印帧数最多的一种。如果仍有多种，则任意一种均可。

样例

样例输入 1

12 20
5 12
6 10
8 1
11 3
5 1
12 4
12 2
11 8
2 8
6 4
7 11
9 1
8 10
9 6
4 1
2 5
10 3
7 2
8 4
9 10

样例输出 1

3 4
3 6 9 10
11 4 1 8
7 12 5 2

样例输入 2

3 3
1 2
2 3
3 1

样例输出 2

1 3
1 2 3

样例输入 3

4 3
1 2
2 3
4 3

样例输出 3

4 1
1
2
3
4