Lyra 对图的对称性很有研究，她格外喜欢一类对称性很强的图，记为 $D_k$，其中 $k$ 是一个非负整数，$D_k$ 是一个有 $2^k$ 个节点的图，若把节点编号为 $0 \sim 2^k -1$，则两个节点之间连边当且仅当两个节点的编号的异或是某 $2$ 的次幂。

Lyra 还特别喜欢研究图的乘积，记 $G_1=(V_1,E_1), G_2=(V_2,E_2)$，则 $G_1 \times G_2$ 定义为

$\left(V_1 \times V_2, \{\left((u_1,u_2),(v_1,v_2)\right) \in (G_1 \times G_2)^2 | u_1=v_1 \wedge (u_2,v_2) \in E_2 \vee u_2=v_2 \wedge (u_1,v_1) \in E_1\}\right)$

即对点做笛卡尔积后，两个新点之间连边当前仅当其中一个点在对应原图中相同，另一个点在原图中有直接连边。

Lyra 曾经有一个 Evan 送给她的无向图 $G$ 可惜她把这个图弄丢了，现在 Lyra 只能通过以前的实验数据来推测 $G$。

Lyra 有一个图 $H$，且已知其同构于 $G \times D_k$，并且可以假设不存在任何大于零的整数 $k_1$ 和无向图 $G_1$ 使得 $G_1 \times D_{k_1}$ 同构与 $G$。

Lyra 想请你还原出 $G$ 并向她证明这确实是一个可行的 $G$，为此，你要找出可行的 $k$ 并对 $H$ 进行重标号。

输入格式

第一行两个整数 $n, m$ 表示点数和边树。

接下来 $m$ 行每行两个整数 $u, v$ 表示一条无向边。

输出格式

第一行输出一个整数 $k$ 表示找到的 $k$。

接下来 $n$ 行，每行一个整数 $t_i$ 和一个长度为 $k$ 的 $01$ 串 $s_i$。

要求：

每个 $[1,\frac{n}{2^k}]$ 内的整数都要在 $t_i$ 中出现恰好 $2^k$ 次。

每个长度为 $k$ 的 $01$ 串要在 $s_i$ 中出现恰好 $\frac{n}{2^k}$ 次。

$(t_i,s_i)$ 有序对不存在重复。

存在一个点数 $\frac{n}{2^k}$ 的图 $G=([1,\frac{n}{2^k}], E)$，对于任意两个点 $u,v$：$u,v$ 之间有边当且仅当 $(t_u,t_v) \in E \wedge s_u=s_v$ 或 $t_u=t_v \wedge s_u \oplus s_v = 2^p$。（$p$ 为任意非负整数，$\oplus$ 表示异或）。

样例输入输出

样例输入1

4 4
1 2
3 4
1 4
2 3

2
1 00
1 01
1 11
1 10

样例输入2

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

样例输出2

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

样例输入3

见 $\texttt{/equipoise/ex_equipoise3.in}$

样例输出3

见 $\texttt{/equipoise/ex_equipoise3.ans}$

数据范围及约定

对于全部数据 $1 \leq n,m \leq 2 \times 10^5$.

令 $K$ 表示答案中可行的 $k$。

Subtask 1[9pts]:}

$n \leq 20.$

Subtask 2[13pts]:}

$n \leq 100.$

Subtask 3[10pts]:}

$n = 2^K \leq 1000.$

Subtask 4[25pts]:}

$n \leq 1000.$

Subtask 5[10pts]:}

$n = 2^K \leq 10^5.$

Subtask 6[33pts]:}

$n \leq 10^5.$

时间限制：$1\texttt{s}$

空间限制：$666\texttt{MB}$

下载

样例数据下载