OI题库

【题目描述】

John是一家中等规模私有企业的CEO。公司的老板决定让他的儿子Scott做公司经理。John害怕如果Scott干的漂亮，老板就会让他夺走自己的职位，因此他决定仔细挑选Scott将要管理的团队来让这位新经理的人生尽量艰难……

John知道他手下的哪些人之间有大仇，导致这两个人在同一团队干活时会非常捉急。John为一个团队定义了一个艰难系数，即大仇的总数除以人数。显然艰难系数越大这个团队就越难管理。John希望找到一组最难管理的员工作为Scott的团队。请帮助他。

图中展示了一个例子，最难管理的团队包含了编号为1，2，4，5的人。在这四个人中有五对人有大仇，因此艰难系数就是5/4.如果我们把3加进去，艰难系数就变成了6/5.

【输入格式】

输入文件的第一行包含了两个整数n,m（1<=n<=100,0<=m<=1000）.这里n是员工总数（员工从1到n编号），m是大仇的数量。

接下来的m行每行包含两个整数ai,bi（1<=ai,bi<=n,ai≠bi），表示ai,bi之间有大仇。同一对人不会出现两次。

【输出格式】

先输出一个正整数k（1<=k<=n），即最难管理的团队人数。接下来有k行每行一个整数，它们按递增顺序给出了最难管理的团队中的人员编号。

如果有多组解，输出任意一组。

【样例输入】

sample input #1

5 6

1 5

5 4

4 2

2 5

1 2

3 1

sample input #2

4 0

【样例输出】

sample output #1

4

1

2

4

5

sample output #2

1

1

【提示】

（原注：在第二个样例中，没有人之间有大仇，即艰难系数为零。因此任意一个非空集合都是合法的。）

由于没有评测插件，在遇到这种情况时请输出一个仅有1号员工的集合，就像样例2一样。

【来源】

Northeastern Europe 2006(NEERC 2006)

POJ 3155 Hard Life