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####样例输出1
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}$
