数年前、この問題の作者は、ある学校の競技会で次の問題を出題しました。「最小次数が $2$ 以上である連結な無向グラフから、隣接する 2 頂点を削除し、連結性が保たれるようにせよ」。しかし、この問題は 2020 年の学生向け競技会には簡単すぎるので、今回は次の問題を考えます。

自己ループも多重辺もなく、少なくとも 3 頂点を持つ連結な無向グラフが与えられます。各辺について、その両端の頂点をともに削除したとき、グラフの連結性が保たれるかどうかを判定してください。

この問題では、グラフに次数 $1$ の頂点が含まれることはありますが、次数 $0$ の頂点は含まれないことに注意してください（連結で、少なくとも 3 頂点があるためです）。

入力

入力の最初の行には、頂点数と辺数をそれぞれ表す 2 つの整数 $n,m$（$3 \le n \le 3 \cdot 10^5$、$n-1 \le m \le 3 \cdot 10^5$）が与えられます。続く $m$ 行のうち $i$ 行目には、$i$ 番目の辺の両端を表す、空白で区切られた 2 つの整数 $x,y$（$1 \le x,y \le n$、$x \ne y$）が与えられます。グラフは連結であり、多重辺を含まないことが保証されます。

出力

長さ $m$ の二進文字列を 1 つ出力してください。答えの $i$ 番目の文字は、$i$ 番目の辺の両端の頂点を削除するとグラフが非連結になる場合には 0、そうでない場合には 1 としてください（引用符は付けません）。

入出力例

入力 1

4 4
1 2
2 3
3 1
4 1

出力 1

0101

注記

削除されるのは辺そのものだけでなく、その両端の頂点もであることに注意してください。したがって、この問題は橋を見つける問題とは異なります。

例えば、入力例の辺 $1$–$2$ は橋ではありませんが、頂点 $1$ と $2$ を削除するとグラフは非連結になります。残ったグラフは、孤立した 2 頂点 $3$ と $4$ からなります。

一方、辺 $1$–$4$ は橋ですが、頂点 $1$ と $4$ を削除するとグラフは連結になります。残ったグラフは、辺 $2$–$3$ によって結ばれた 2 頂点 $2$ と $3$ からなります。