Extra
Time
2015.8.12 noip模拟赛——选学霸 Time:1s Memory:50M AC:17% Submit:12

题目描述

XX 的老师想从 N 名学生中选 M 人当学霸,但有 K 对人
实力相当,如果实力相当的人中,一部分被选上,另一部分
没有,同学们就会抗议。所以老师想请你帮他求出他该选多
少学霸,才能既不让同学们抗议,又与原来的 M 尽可能接近 输入格式
第一行,三个正整数 N,M,K。
第 2...K 行,每行 2 个数,表示一对实力相当的人的
编号(编号为 1…N) 输出格式
一行,表示既不让同学们抗议,又与原来的 M 尽可能
接近的选出学霸的数目。(如果有两种方案与 M 的差的绝对
值相等,选较小的一种

样例输入 1

4 3 2
1 2
3 4

样例输出 1

2

样例输入 2

4 3 2
1 2
2 3

样例输出 2

3

数据规模

对于 40%的数据:n<=100
对于 100%的数据:n<=5000