问题 1269 --数据结构-图-珍珠

1269: 数据结构-图-珍珠★★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 126  解决: 87
[提交][状态][命题人:]

题目描述

有 n 颗形状和大小都一致的珍珠,它们的重量都不相同。n 为整数,所有的珍珠从 1 到 n 编号。你的任务是发现哪颗珍珠的重量刚好处于正中间,即在所有珍珠的重量中,该珍珠 的重量列(n+1)/2 位。下面给出将一对珍珠进行比较的办法:  给你一架天平用来比较珍珠的重量,我们可以比出两个珍珠哪个更重一些,在作出一系 列的比较后,我们可以将某些肯定不具备中间重量的珍珠拿走。 例如,下列给出对 5 颗珍珠进行四次比较的情况: 

1、 珍珠 2 比珍珠 1 重 

2、 珍珠 4 比珍珠 3 重 

3、 珍珠 5 比珍珠 1 重 

4、 珍珠 4 比珍珠 2 重 

根据以上结果,虽然我们不能精确地找出哪个珍珠具有中间重量,但我们可以肯定珍珠 1 和珍珠 4 不可能具有中间重量,因为珍珠 2、4、5 比珍珠 1 重,而珍珠 1、2、3 比珍珠 4 轻,所以我们可以移走这两颗珍珠。 写一个程序统计出共有多少颗珍珠肯定不会是中间重量。

输入

输入文件第一行包含两个用空格隔开的整数 N 和 M,其中 1<=N<=99,且 N 为奇数, M 表示对珍珠进行的比较次数,接下来的 M 行每行包含两个用空格隔开的整数 x 和 y,表 示珍珠 x 比珍珠 y 重。

输出

输出文件仅一行包含一个整数,表示不可能是中间重量的珍珠的总数。
样例输入
Copy
5 4
2 1
4 3
5 1
4 2
样例输出
Copy
2

提示

来源

 

[提交][状态]