给你一个拥有 $n$ 个顶点和 $m$ 条边的图 $P$。你需要将其分解为某个图 $Q$ 与一个具有最大幂 $k$ 的布尔立方体图的笛卡尔积。

幂为 $k$ 的布尔立方体图是一个拥有 $2^k$ 个顶点的图，顶点编号从 $0$ 到 $2^k - 1$。当且仅当两个顶点的二进制表示（含前导零）恰好在一位上不同时，这两个顶点相邻。

图 $G$ 和 $H$ 的笛卡尔积 $G \square H$ 是一个满足以下条件的图：

1. $G \square H$ 的顶点集是集合 $V(G) \times V(H)$ 的笛卡尔积。

2. $G \square H$ 中的任意两个顶点 $(u, u')$ 和 $(v, v')$ 相邻，当且仅当满足以下条件之一：

   • $u = v$ 且 $u'$ 在 $H$ 中与 $v'$ 相邻，或者
   • $u' = v'$ 且 $u$ 在 $G$ 中与 $v$ 相邻。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n \le 2 \cdot 10^5, 0 \le m \le 2 \cdot 10^5$) —— 图 $P$ 的顶点数和边数。

接下来的 $m$ 行，每行包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \ne b_i$)，描述第 $i$ 条边。

保证任意两个顶点之间最多只有一条边。

输出格式

第一行应包含一个整数 $k$。

如果 $k > 0$，则接下来输出 $n$ 行。其中第 $i$ 行应包含一个整数 $1 \le c_i \le \frac{n}{2^k}$ 和一个长度为 $k$ 的二进制字符串，分别表示图 $Q$ 中的顶点编号以及用于生成图 $P$ 中第 $i$ 个顶点的布尔立方体顶点的描述。

换句话说，你应该描述输入图的顶点与二元组 $(u, v)$ 之间的双射，其中 $u$ 是图 $Q$ 的顶点，而 $v$ 是布尔立方体图的顶点。

样例

输入格式 1

4 4
1 3
3 2
2 4
4 1

输出格式 1

2
1 00
1 11
1 01
1 10

输入格式 2

6 9
1 4
2 5
3 6
1 2
1 3
2 3
4 6
5 6
4 5

输出格式 2

1
1 0
3 0
2 0
1 1
3 1
2 1

输入格式 3

3 3
1 2
2 3
1 3

输出格式 3

0

说明

在数学中，笛卡尔积是一种数学运算，它返回多个集合的乘积集合（或简称积）。也就是说，对于集合 $A$ 和 $B$，笛卡尔积 $A \times B$ 是所有有序对 $(a, b)$ 的集合，其中 $a \in A$ 且 $b \in B$。（维基百科）