#433. 二分图判定

二分图判定

描述

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

输入

多组数据。每组数据:

  • 第一行:两个整数 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≤15N\leq 15;

对于 40% 的数据有 N≤2,000,M≤50,000N\leq 2,000,M\leq 50,000;

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

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

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