3408 - 判断二分图

题目描述

存在一个 无向图 ,图中有 n 个节点。其中每个节点都有一个介于1 到 n  之间的唯一编号。

给定一个n个节点,e条边的无向图。

该无向图同时具有以下属性:

(1)不存在自环。

(2)不存在平行边。

请判断是否为二分图,如果图是二分图,返回 true ;否则,返回 false

二分图 定义:如果能将一个图的节点集合分割成两个独立的子集 A 和 B ,并使图中的每一条边的两个节点一个来自 A 集合,一个来自 B 集合,就将这个图称为 二分图 。

输入

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

接下来e行,每行有2个数,代表这两个结点之间有一条边。(1<=n,e<=2e5)

输出

如果图是二分图,返回 true ;否则,返回 false 。

样例

输入

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

输出

false

输入

4 4
1 2
1 4
2 3
3 4

输出

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


上一题 下一题