选学霸

题目描述

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

输入输出格式

输入格式


第一行,三个正整数 $n,m,k$。 接下来 $k$ 行,每行 $2$ 个数,表示一对实力相当的人的编号(编号为 $1,2,\cdots n$)。

输出格式


共一行,表示既不让同学们抗议,又与原来的 $m$ 尽可能接近的选出学霸的数目。 如果有两种方案与 $m$ 的差的绝对值相等,选较小的一种。

输入输出样例

输入样例 #1

4 3 2
1 2
3 4

输出样例 #1

2

说明

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