P3425 [POI 2005] KOS-Dicing

掷骰子是一种双人游戏，它的结果是完全随机的。最近它在整个 Byteotia 变得非常流行。在 Byteotia 的首都甚至有一个特别的掷骰子业余爱好者俱乐部。俱乐部的老主顾们花时间互相聊天并每隔一阵子就和一个随机选择的对手玩这他们最喜欢的游戏。一天中赢得最多游戏的人会得到“幸运者”头衔。有时晚上俱乐部很安静，只有很少的比赛。这是哪怕赢一场也能获得“幸运者”头衔的时间。 很久很久以前有一个很不走运的人，叫 Byteasar，赢得了这个光荣的头衔。他被深深地震惊了以至于完全忘了他已经赢了多少场。现在他想知道他有多幸运，以及幸运之神是否最终会向他微笑——也许他的运气会变好？他确切地知道在那个幸运的晚上有多少场游戏以及是谁玩的。然而，他不知道结果。Byteasar 希望查明至少要赢几场才能获得“幸运者”头衔。做个好人，帮他满足他的好奇心吧！ - - - 写一个程序： 对于每场游戏读入这场游戏的一对玩家。 找到最小的数 $k$，使得存在一个游戏结果的集合，其中赢最多的玩家赢了 $k$ 场。 输出数 $k$ 和找到的集合中游戏的结果。 玩家从 $1$ 到 $n$ 编号。

第一行有两个整数 $n,m$（$1\le n,m\le 10^4$）。$n$ 表示玩家数，$m$ 表示游戏数。由一个空格分开。 接下来的 $m$ 行，第 $i$ 行表示第 $i$ 场游戏的玩家编号 $(a_i,b_i)$，由一个空格分开。 一对玩家可能会在这个序列中多次出现。

第一行应该包含一个确定的数 $k$。 对于在输入的第 $i$ 行指定的一对玩家 $(a_i,b_i)$，如果在找到的结果集合中 $a_i$ 胜过 $b_i$，则在输出的第 $i$ 行输出 `1`, 否则输出 `0`。

$1\le n,m\le 10^4$。 样例：