考虑以下在无向图中寻找连通分量的算法：

• 对于每个顶点 $i$（顶点编号从 $1$ 到 $n$），定义 $c_i = i$。
• 重复执行以下步骤：
  • 遍历图中的所有边 $(a, b)$，并令 $c_a = c_b = \min(c_a, c_b)$。
  • 如果上一轮对所有边的遍历没有改变任何 $c_i$ 的值，则停止算法。

不难发现，该算法在主循环最多执行 $n$ 次后会终止。然而，顶点的顺序和边的顺序是有影响的。给定一个图，你需要重新编号其顶点，并重新排列其边，使得该算法在主循环中执行的次数尽可能多。

输入格式

输入文件的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 100, 1 \le m \le 4950$)，分别表示图中的顶点数和边数。接下来的 $m$ 行描述了这些边，每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le n, a \neq b$)，表示由该边连接的两个顶点。任意一对顶点之间最多只有一条边，且没有边连接顶点自身。

输出格式

输出文件的第一行打印上述算法主循环的最大迭代次数。

输出文件的第二行打印 $n$ 个空格分隔的互不相同的整数（范围在 $1$ 到 $n$ 之间），描述你所选择的顶点顺序：第一个数应该是你声明为顶点 $1$ 的输入文件中的顶点编号，第二个数应该是你声明为顶点 $2$ 的输入文件中的顶点编号，以此类推。

输出文件的第三行打印 $m$ 个空格分隔的互不相同的整数（范围在 $1$ 到 $m$ 之间），描述你所选择的边顺序：第一个数应该是你声明为边 $1$ 的输入文件中的边编号，第二个数应该是你声明为边 $2$ 的输入文件中的边编号，以此类推。算法将按照你给出的顺序遍历这些边。

如果有多种方案能达到最大迭代次数，输出任意一种即可。

样例

输入 1

3 2
1 2
1 3

输出 1

3
2 1 3
2 1

说明

在样例中，我们将旧的顶点编号 $2$ 重新编号为 $1$，旧的顶点编号 $1$ 重新编号为 $2$，并将旧的顶点编号 $3$ 保持为 $3$。此时我们的边连接了顶点 $1$ 与顶点 $2$，以及顶点 $2$ 与顶点 $3$，并且我们在第一条边之前处理第二条边。

我们从以下 $c_i$ 的值开始：$1, 2, 3$。

在主循环的第一次迭代中，我们首先处理连接顶点 $2$ 和顶点 $3$ 的边，此时 $c_i$ 变为 $1, 2, 2$；然后我们处理连接顶点 $1$ 和顶点 $2$ 的边，此时 $c_i$ 变为 $1, 1, 2$。

在主循环的第二次迭代中，我们首先处理连接顶点 $2$ 和顶点 $3$ 的边，此时 $c_i$ 变为 $1, 1, 1$；然后我们处理连接顶点 $1$ 和顶点 $2$ 的边，此时 $c_i$ 保持为 $1, 1, 1$。

在主循环的第三次迭代中，没有任何值发生改变，算法停止。