返回小组 开始 2026-10-04 08:40:00

图论搜索专项练习

结束 2026-10-04 12:30:00
Contest is over.
当前 2026-10-11 11:57:18

A. 二分图的判定

描述

给定一张1~n编号,m条边的无向图。请判断是否是二分图,如果是,请输出任意一种满足二分图定义的两个子集

输入

第一行两个数字n,m

接下来m行,每行2个数字,表示两个编号的顶点之间有一条边

输出

第一行输出 true or false,表示是否为二分图。

如果是,那么再输出两行,每行两个集合,表示两个子集内的所有点的编号

样例

输入

4 4
4 1
4 2
4 3
2 3

输出

false

输入

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

输出

true
1 2 3
4 5

提示

n\leq 1000, m\leq 10000


Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交