题意简述

军团长想要从 $N$ 名士兵（编号为 $1 \ldots N$）中选出 $M$ 名士兵当队长。$N$ 名士兵中有 $C$ 对士兵实力相同，如果实力相同的士兵中一部分被选为队长，另一部分没有被选为队长，就会引起士兵们的抗议，甚至哗变。军团长想知道，如何选队长才能既避免士兵们抗议，又能选出尽量接近 $M$ 名队长。

输入格式

第 $1$ 行：三个空格分隔的整数 $N$、$M$ 和 $C$。

接下来 $C$ 行：每行两个空格分隔的正整数 $x$ 和 $y$，表示编号为 $x$ 和编号为 $y$ 的士兵实力相同。

输出格式

一行：表示可以选出的既不让士兵们抗议，又与 $M$ 尽量接近的队长数量。如果有两种方案和 $M$ 的差值相同，那么优选选择队长数量较小的方案。

输入输出样例

• 输入样例 $1$：

5 3 3
1 2
2 3
3 4

• 输出样例 $1$：

4

说明

• $1 \le M \le N \le 10^4$。

• $1 \le x,y \le N$。

• $1 \le C \le 10^4$。