#P50883. 「CEOI2015 Day2」又是卡尔文球锦标赛

「CEOI2015 Day2」又是卡尔文球锦标赛

Cannot parse: undefinedms error parsing time

题目描述

译自 CEOI2015 Day2 T3「Calvinball championship, again

还记得吗?一场卡尔文球比赛会有 nn 名选手参与,分为若干个非空的球队。

但是选手之间可能有私仇,如果 aa 不喜欢 bb,那么 bb 也不喜欢 aa

所以我们决定在比赛前的最后一刻再次调整球队:互相讨厌的人不能在一个球队,且要在满足该条件的同时使得球队尽量少。

还是举个栗子:譬如有 6 个玩家, 6 号选手不喜欢其他所有人,3 号选手不喜欢 2 号和 5 号选手。那么最少可以以三个队伍举行比赛(例如:6 号万年单身,4 号和 3 号一队,1 号、2 号和 5 号一队),但不能以两个队伍(因为 6 号、3 号和 2 号互相讨厌彼此,所以必须分开),也不能以四个队伍(因为有更优的方案)。

描述各个选手不喜欢的选手,请找到一些分配队伍的合法方案(如果有几个的话,任意一个)。

输入格式

这是一道提交答案题目,你可以在附加文件中下载到输入数据。每个数据都按照以下格式。

第一行,两个非负整数 nnmm,分别表示选手的数量和选手之间互相不喜欢的关系的数量。选手编号为 1,,n1,\dots,n

以下 mm 行中,第 ii 行有两个不同的正整数 aia_ibi(1ai,bin)b_i(1 \leq a_i,b_i \leq n),表示选手 aia_i 和选手 bib_i 互相不喜欢。

输出格式

第一行,一个非负整数 tt,表示可以分成的队伍数量。

以下 tt 行中,第 ii 行包含一个以空格分隔的列表,表示列表中的选手全部属于第 ii 个队伍。队伍和队员可以按照个人喜好排列。

样例

6 7
1 6
2 6
3 6
4 6
5 6
5 4
2 4
3
6
4 3
1 2 5

一种可能的正确输出为:

该样例对应以上题目描述中的栗子。

数据范围与提示

你可以在附加文件中下载到输入文件,请注意,提交所使用的文件名与对应的输入文件名相同,但后缀名不同。例:输入文件 calvin.6 对应你提交的 zip 文件中的 calvin.6.out 文件。在提交正确的输出文件中,每个正确的输出文件可以使你获得 10 分。