P2668体重 | |
|
Description
近日,信竞班有人在散布谣言,说何老板体重超重,这有损何老板在同学们心中的完美形象,让何老板很是头疼。何老板还了解到,散布该谣言的人号称自己拥有最合适的体重,体重值位于所有人的正中间,何老板决心找出这个家伙。
信竞班有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重,所以他可以排除到这两名同学。
写一个程序统计出目前我们最多能排除掉多少个同学。也就是确定有多少个同学肯定不会是中间体重。
Input Format
第一行:两个整数n和m,其中n为奇数表示学生总数,m表示何老板搜集到的信息条数。
接下来的m行,每行两个整数x和y,表示x号同学比y号同学重。
Output Format
若干个整数,按从小到大的顺序输出不可能是中间重量的学生的编号。
若一个也找不出来,输出0。
Sample Input 1
5 4
2 1
4 3
5 1
4 2
Sample Output 1
1 4
Sample Input 2
11 5
1 2
3 4
5 6
7 8
9 10
Sample Output 2
0
Sample Input 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
Sample Output 3
1
Hint
1<=n<=100
1<=m<=5000