题目描述(ID:12400)
标题: 判断二分图
标签: 图结构 二分图
详情: 啊哈星球上有n个城市,城市与城市之间有m条道路,现在要将n个城市分为两组,每组城市间互不相通(即没有道路可以直接到达彼此的城市),如果能分成两组,输出两组城市的编号,按字典序输出,如果不能分成两组,输出NO。
输入格式:
第一行输入n个顶点和m条边,接下来输入m行,每行两个整数x、y,表示一条从x城市与y城市之间有道路连通。
输出格式:
如果不能分成两组输出NO,如果可以分成两组,输出两行,表示分组的情况,按字典序输出,城市编号与城市编号之间用空格隔开。
提示: 1<=n<=1000 1<=m<=6000 1<=x,y<=1000
样例:

输入

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

输出

NO

输入

6 4
1 2
3 4
3 6
4 5

输出

1 3 5
2 4 6
登录并解答