描述

判断一个图是否为二分图。

输入

多组数据。每组数据：

• 第一行：两个整数 N, M，其中 N 表示点数（点的编号从 1 ~ N），M 表示边数
• 接下来 M 行：每行两个整数 u , v 表示点 u 和点 v 之间有一条无向边。可能有重边。

输出

每组数据的答案占一行，如果是二分图输出 1 否则输出 0

样例输入

3 3
1 2
2 3
3 1
3 3
1 2
1 3
3 1

样例输出

0
1

数据范围

对于 20% 的数据有 $N\leq 15$；

对于 40% 的数据有 $N\leq 2,000，M\leq 50,000$；

对于 60% 的数据有 $N\leq 20,000，M\leq 100,000$。

对于 100% 的数据有 $N\leq 100,000，M\leq 200,000$。

每个数据点均不超过 10 组数据。