Description

现在有一场国家级的OI团体赛，s省要从 $n$ 个人中选出 $v$ 个人组队参赛，这 $x$ 个人中有 $x$ 对人本身在省内就是一个学校的，因此在一个学校的同学要么都选，要么都不选。请你编程选出尽可能和 $v$ 接近的人数。

Input

第一行，三个正整数 $n$,$v$,$m$。 接下来$m$行,每行$2$个数，表示在省内就在一个学校的$2$个人的编号（编号为$1$,$2$,$...$,$n$）。不保证两个人编号不同。

Output

一行，与原来的$v$尽可能接近的选出的人数。 如果有两种方案与$v$的差的绝对值相等，选较小的一种。

Samples

6 3 3
1 2
3 4
5 6

2

Limitation

对于30%的数据：$1\leq n\leq 2\times {10}^4$

对于60%的数据：$1\leq n\leq 2\times {10}^5$

对于100%的数据：

$1\leq m\leq n\leq1\times {10}^6$