暂无测试数据。

百奇班上最近流行一个有趣的游戏。

对于一个 $R$ 行 $C$ 列的表格，每个格子中有一个数，或者是 $0$，或者是 $1$。我们如下定义它的关联图：

1. 对于一个 $8$ 连通的连通块，如果所有格子的值都相同，那么它们在关联图中对应着同一个结点。
2. 对于任意两个相邻的连通块，关联图中有一条边连接他们对应的结点。

格子中的两个位置在 $8$ 连通意义下相邻指的是它们有共同的边或顶点。

我们称格子 $a$ 和格子 $b$ 连通，当且仅当 $a$ 和 $b$ 相邻，或者存在一个格子 $c$，使得 $a$ 和 $c$ 连通且 $b$ 和 $c$ 连通。

我们称一个非空的格子集合 $S$ 是一个连通块，当且仅当这个集合里任意两个不同格子都是连通的。

这个游戏是这样的，其中一方会给出一个图，另一方需要找到关联图与这个图同构的表格，或者判断出没有这样的表格，即可以获得胜利。

我们定义两个图 $A$ 和 $B$ 同构，指存在一种将图 $A$ 重编号的方案，使得 $A$ 的点集和边集和 $B$ 的完全相同。

百奇不太擅长这个游戏，所以他找到你来帮忙完成。

输入格式

第一行输入两个整数 $n,m$，分别表示关联图的点数和边数。

下接 $m$ 行，每行两个数 $u,v$，表示关联图中的一条边。

相邻两个数之间用一个空格隔开。

输出格式

第一行输出两个整数 $R,C$，表示表格的行数和列数。（需要保证 $R\times C \leq 10^5$）

下接 $R$ 行，每行 $C$ 个数，$0$ 或者 $1$，表示矩阵。

相邻两个数之间用一个空格隔开。

如果无解输出 $-1$。

数据范围

对于 $30\%$ 的数据，一定存在一组解，使得 $R \times C \leq 10$。

对于另外 $20\%$ 的数据，关联图为一条链。

对于 $100\%$ 的数据，$1 \leq n \leq 50,\ 0 \leq m \leq \frac{n(n-1)}{2},\ 1 \leq u,v \leq n$。

3 2
1 2
1 3

1 3
1 0 1

3 3
1 2
1 3
2 3

-1