3409 - 可能的二分法

题目描述

给定一组 n 人(编号为 1, 2, ..., n), 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人,那么他们不应该属于同一组。

给定整数 n 和e条信息(包含ai, bi) ,其中ai ,bi表示不允许将编号为 ai 和  bi的人归入同一组。当可以用这种方法将所有人分进两组时,返回 true;否则返回 false。

输入

第一行两个整数,n和e,表示有n个结点(结点编号为1~n),e条信息。

接下来e行,每行有2个数ai,bi。(1<=n,e<=2e5)

输出

当可以用这种方法将所有人分进两组时,返回 true ;否则,返回 false 。

样例

输入

4 3
1 2
1 3
2 4

输出

true

输入

3 3
1 2 
1 3
2 3

输出

false

输入

5 5
1 2
2 3
3 4
4 5
1 5

输出

false
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过人数 1
金币数量 3 枚
难度 未标记


上一题 下一题