K. 选学霸

Type: RemoteJudge

1000ms

128MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

老师想从 $n$ 名学生中选 $m$ 人当学霸，但有 $k$ 对人实力相当，如果实力相当的人中，一部分被选上，另一部分没有，同学们就会抗议。所以老师想请你帮他求出他该选多少学霸，才能既不让同学们抗议，又与原来的 $m$ 尽可能接近。

第一行，三个正整数 $n,m,k$ 。

接下来 $k$ 行，每行 $2$ 个数，表示一对实力相当的人的编号（编号为 $1,2,\cdots n$ ）。

共一行，表示既不让同学们抗议，又与原来的 $m$ 尽可能接近的选出学霸的数目。

如果有两种方案与 $m$ 的差的绝对值相等，选较小的一种。

4 3 2
1 2
3 4

对于 $100\%$ 的数据，满足 $1 \le n,m \le 2 \times 10^4$ 。