5037 - 图论:二分图:飞机驾驶员

第二次世界大战期间,英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的两名飞行员,其中一名是英国飞行员,另一名是外籍飞行员。在众多的飞行员中,每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。一共有 n 个飞行员,其中有 m 个外籍飞行员和 (n−m) 个英国飞行员,外籍飞行员从 1到 m 编号,英国飞行员从 m+1 到 n 编号。 对于给定的外籍飞行员与英国飞行员的配合情况,试设计一个算法找出最佳飞行员配对方案,使皇家空军一次能派出最多的飞机。

输入

输入的第一行是用空格隔开的两个正整数,分别代表外籍飞行员的个数 m 和飞行员总数 n。 从第二行起到倒数第二行,每行有两个整数 u,v,代表外籍飞行员 u 可以和英国飞行员 v 配合。 输入的最后一行保证为 -1 -1,代表输入结束。

输出

请输出能派出最多的飞机数量

样例

输入

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

输出

4

提示

数据范围与约定

对于100% 的数据,保证 1≤m≤n<100,1≤u≤m<v≤n,同一组配对关系只会给出一次。 【提示】

请注意输入的第一行先读入 m,再读入 n。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题