OI题库

问题描述
随着资本的扩大，藏宝海湾贸易亲王在卡利姆多和东部王国大陆各建立了N/2 个港口。大灾变发生以后，这些港口之间失去了联系，相继脱离了藏宝海湾贸易亲王的管辖，各自为政。利益的驱动使得每个港口都想和对岸大陆的另一个港口建立贸易合作关系，由于地理位置因素，只有存在直接到达的航线的两个港口才能建立合作，而且每个港口只与对岸一个港口建立合作，因此并不是所有的港口都能找到合作伙伴。
 
血帆海盗得知这一消息以后，决定对其中一条航线进行干扰性的掠夺。经过分析，血帆海盗计算出最多能有W 对港口合作。如果两个港口之间只有一条航线，而且这条航线恰好是血帆海盗要掠夺的航线，这两个港口将不能建立合作关系。血帆海盗指挥官菲尔拉伦想知道他们有几种选择，可以让地精们无法建立W 对港口。

输入格式
第1行，两个整数N,M，表示一共的港口个数和航线条数。
接下来M行，每行两个整数A,B，表示卡利姆多的港口A与东部王国的港口B之间有一条航线直接连接，其中1<=A<=N/2，N/2+1<=B<=N。

输出格式
一个整数，表示血帆海盗可以选择掠夺的航线条数。
 
解释：如果掠夺一条航线以后，地精依然可以建立起最多的W个合作关系（可以有多种），
那么这条航线是不值得掠夺的，否则就是掠夺方案之一。

样例输入
8 5
1 5
1 6
2 7
3 7
4 8

样例输出
1

样例说明
地精做多能建立起合作关系的数量为3，掠夺(4,8)这条航线后，最多能建立的合作关系的
数量减少为2。

数据规模
40%的数据满足2<=N<=200，1<=M<=1000
100%的数据满足2<=N<=100000，1<=M<=100000，保证N为偶数

 

by   BYVoid