[NERRC 2006][POJ3155]生活的艰辛

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file hardlife.in Output file hardlife.out

【题目描述】

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