Description

The teacher wants to select $m$ students out of $n$ to be top students, but there are $k$ pairs of students who are equally strong. If, among students of equal strength, some are selected while others are not, the class will protest. Therefore, the teacher asks you to determine how many top students he should select so that there is no protest and the number is as close as possible to the original $m$.

Input Format

The first line contains three positive integers $n, m, k$.

The next $k$ lines each contain $2$ numbers, representing the IDs of a pair of equally strong students (IDs are $1, 2, \cdots, n$).

Output Format

Output a single line: the number of top students to select such that there is no protest and the number is as close as possible to the original $m$.

If there are two options whose absolute difference from $m$ is the same, choose the smaller one.

4 3 2
1 2
3 4

2

Hint

For $100\%$ of the testdata, it holds that $1 \le n \le 2 \times 10^4, 0 \le m \le n, 0 \le k \le 2 \times 10^4$.

Translated by ChatGPT 5