掷骰子是一种双人游戏，其结果完全随机。最近，它在 Byteotia 全境的流行度不断攀升。Byteotia 的首都甚至有一个专门的掷骰子爱好者俱乐部。俱乐部的常客们在闲聊之余，偶尔会与随机挑选的对手进行他们最喜爱的游戏。每天赢得比赛场次最多的人将获得“幸运儿”的称号。有时俱乐部之夜比较冷清，进行的比赛很少，在这种情况下，哪怕只赢一场比赛也可能让你成为“幸运儿”。

从前，一个极其倒霉的家伙 Byteasar 竟然赢得了这个光荣的称号。他对此感到无比震惊，以至于完全忘记了自己到底赢了多少场比赛。现在，他想知道自己的运气究竟有多好，命运是否终于对他露出了微笑——也许他的运气真的彻底好转了？他清楚地知道那个幸运之夜进行了多少场比赛以及每场比赛的对阵双方，但他不知道比赛结果。Byteasar 希望找出能让他获得“幸运儿”称号的最小胜场数。请帮帮他，满足他的好奇心！

编写一个程序：

• 对于每一场比赛，从标准输入读取对阵双方的编号。
• 找到最小的整数 $k$，使得存在一种比赛结果分配方案，满足每位玩家的胜场数都不超过 $k$。
• 将该数字 $k$ 以及找到的比赛结果输出到标准输出。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$，中间用空格隔开，$1 \le n \le 10\,000$，$0 \le m \le 10\,000$；其中 $n$ 表示玩家人数，$m$ 表示比赛场次。玩家编号从 $1$ 到 $n$。接下来的 $m$ 行每行包含一对玩家编号，表示比赛序列，中间用空格隔开。同一对玩家可能在序列中多次出现。

输出格式

标准输出的第一行应包含确定的最小胜场数 $k$。对于输入中第 $i$ 行指定的玩家 $a$ 和 $b$ 的对阵，输出的第 $i$ 行应写入数字 $1$（如果玩家 $a$ 在找到的结果集中战胜了玩家 $b$）或 $0$（否则）。

样例

输入 1

4 4
1 2
1 3
1 4
1 2

输出 1

1
0
0
0
1