树 $T$ 的平方 $T^2$ 定义为一个简单的无向图，其顶点集与 $T$ 相同，边集通过以下方式扩充：当且仅当 $T$ 中存在长度不超过 2 的路径连接两个顶点时，这两个顶点在 $T^2$ 中相邻。也就是说，其顶点集与 $T$ 相同，边集为 $\{(u, v) : d_T(u, v) \le 2\}$，其中 $d_T(u, v)$ 表示 $T$ 中 $u$ 和 $v$ 之间的距离。图 I.1 展示了一棵树及其平方。

图 I.1：一棵树 $T$ 及其平方 $T^2$。图中用虚线曲线表示了 $T^2$ 中连接距离 $d_T(u, v) = 2$ 的顶点 $u$ 和 $v$ 的边。

如果一个图 $G$ 是某棵树 $T$ 的平方，即 $G = T^2$，则称 $T$ 是 $G$ 的平方根。对于给定的树 $T$，计算其平方 $T^2$ 是平凡的；然而，对于给定的图 $G$，判断是否存在一棵树 $T$ 使得 $T^2 = G$ 并不平凡。你的任务是编写一个高效的程序，判断给定的图 $G$ 是否存在平方根树。

输入格式

程序从标准输入读取数据。第一行包含两个正整数 $n$ 和 $m$，分别表示输入图 $G$ 的顶点数和边数，其中 $2 \le n \le 100,000$ 且 $m \le 1,000,000$。接下来 $m$ 行，每行包含两个正整数 $u$ 和 $v$，表示 $G$ 中顶点 $u$ 和 $v$ 之间的一条边。假设 $G$ 是一个简单的无向图，顶点编号从 $1$ 到 $n$。

输出格式

程序将结果写入标准输出。第一行必须包含一个整数，表示是否存在一棵树是输入图的平方根。如果存在，该整数必须为 $1$；否则为 $-1$。当且仅当第一行为 $1$ 时，后面必须紧跟该输入图的任意一棵平方根树的描述。树的描述方式为：第一行包含一个整数 $n$，表示顶点数，随后 $n - 1$ 行，每行包含两个正整数 $u$ 和 $v$，表示树中顶点 $u$ 和 $v$ 之间的一条边。

样例

样例输入 1

8 15
1 2
1 3
1 7
2 3
2 4
2 6
2 7
2 8
3 4
3 7
5 6
5 7
6 7
6 8
7 8

样例输出 1

1
8
1 2
2 3
3 4
7 2
5 6
6 7
7 8

样例输入 2

8 14
1 2
1 3
1 7
2 3
2 4
2 6
2 7
2 8
3 4
3 7
5 6
5 7
6 7
6 8

样例输出 2

-1

样例输入 3

5 7
1 2
2 3
3 4
4 5
5 3
4 2
3 1

样例输出 3

1
5
1 2
2 3
3 4
4 5

样例输入 4

4 6
1 2
2 3
3 4
4 1
4 2
3 1

样例输出 4

1
4
2 1
3 1
4 1