TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2668
  • 题目
  • P2668体重
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    近日,信竞班有人在散布谣言,说何老板体重超重,这有损何老板在同学们心中的完美形象,让何老板很是头疼。何老板还了解到,散布该谣言的人号称自己拥有最合适的体重,体重值位于所有人的正中间,何老板决心找出这个家伙。

    信竞班有n名同学,编号1到n,已知每名同学的体重都不相同。何老板想知道,哪个同学的体重位于正中间。也就是如果将n名同学按体重由轻到重排序后,该名同学位于第(n+1)/2名,这名同学一定是谣言散布者。

    但是同学们都不肯准确告诉何老板他的体重,何老板只好在暗中收集信息。

    例如:n=5时,何老板搜集到了如下信息:

        1号同学比2号同学轻

        3号同学比4号同学轻  

        1号同学比5号同学轻  

        2号同学比4号同学轻  

    根据上面的情报,虽然何老板不能准确得出哪个同学具有中间体重,但他可以肯定4号和1号不可能具有中间体重,因为,1、2、3比4轻,而2、4、5比1重,所以他可以排除到这两名同学。


    写一个程序统计出目前我们最多能排除掉多少个同学。也就是确定有多少个同学肯定不会是中间体重。

    输入格式

    第一行:两个整数n和m,其中n为奇数表示学生总数,m表示何老板搜集到的信息条数。

    接下来的m行,每行两个整数x和y,表示x号同学比y号同学重。

    输出格式

    若干个整数,按从小到大的顺序输出不可能是中间重量的学生的编号。
    若一个也找不出来,输出0。

    样例输入 1

    5 4
    2 1
    4 3
    5 1
    4 2

    样例输出 1

    1 4

    样例输入 2

    11 5
    1 2
    3 4
    5 6
    7 8
    9 10

    样例输出 2

    0

    样例输入 3

    31 29
    2 1
    3 1
    4 1
    5 1
    6 1
    7 1
    8 1
    9 1
    10 1
    11 1
    12 1
    13 1
    14 1
    15 1
    16 1
    17 1
    18 1
    19 1
    20 1
    21 1
    22 1
    23 1
    24 1
    25 1
    26 1
    27 1
    28 1
    29 1
    30 1

    样例输出 3

    1

    提示

     

    1<=n<=100

    1<=m<=5000