本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden ☆ before use]

1159. 搭配飞行员


Description

飞行大队有若干个来自各地的驾驶员,专门驾驶一种型号的飞机,这种飞机每架有两个驾驶员,需一个正驾驶员和一个副驾驶员。由于种种原因,例如相互配合的问题,有些驾驶员不能在同一架飞机上飞行,问如何搭配驾驶员才能使出航的飞机最多。因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行。

Input

第一行,两个整数 n 与m,表示共有 n 个飞行员,其中有m名飞行员是正驾驶员。
下面有若干行,每行有 2 个数字 a、b。表示正驾驶员 a 和副驾驶员 b可以同机飞行。
注:正驾驶员的编号在前,即正驾驶员的编号小于副驾驶员的编号。

Output

仅一行一个整数,表示最大起飞的飞机数。

Samples

Input Copy
10 5
1 7
2 6
2 10
3 7
4 8
5 9
Output
4

Hint

n<=100

Source

网络流24题
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 2 / 3
Tags:
Contests involved

1020. 网络流训练1
My history solutions

You didn't submit any solution!
Submit your solution

Login Register