该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

读入一幅有 $n$ 个点 $m$ 条边的简单无向图（即无重边，无自环）。你需要为每个节点赋予一个长度为 $k$ 的 01 串（二进制数），使得原图有连边当且仅当两个节点的值与的结果不为 $0$。

你需要保证你使用的 $k$ 不超过 $\lfloor \frac{n^2}{4} \rfloor$。保证有解。

若有多解，输出任意一解即可。

Format

Input

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

随后 $m$ 行每行两个整数表示一条连边。

点编号从 1 开始。

Output

首先输出一个 $k$ 表示你使用的编码长度。

随后 $n$ 行每行一个长度为 $k$ 的 01 串。

Samples

5 4
1 2
2 3
3 1
3 4

2
10
10
11
01
00

Hints

若构造的方案不合法，你将获得 $0$ 分。

若 $k > \lfloor \frac{n^2}{2} \rfloor$，你将获得 $0$ 分。

若 $\lfloor \frac{n^2}{4} \rfloor < k \le \lfloor \frac{n^2}{2} \rfloor$，你将获得该点 $30\%$ 的分数。

若 $k \le \lfloor \frac{n^2}{4} \rfloor$，你将获得该点 $100\%$ 的分数。

对于 $100\%$ 的数据，$2\le n \le 100$。