有 $n$ 个墨水瓶，编号从 $1$ 到 $n$。这些瓶子最初是空的。前 $m$ 个瓶子被注入了 $m$ 种不同颜色的墨水，且这些墨水瓶之间可以通过软管相互输送墨水。随着墨水的持续注入和混合，瓶中的墨水颜色可能会发生变化，但最终会在一天结束时达到平衡状态，此后颜色不再改变。在平衡状态下，满足以下性质：

• 一个瓶子（设为 A）包含墨水，当且仅当注入前 $m$ 个瓶子的墨水可以通过若干条软管流向 A。否则，A 为空。
• 每个非空瓶子包含单一颜色的墨水。
• 如果一个瓶子（设为 B）从多个墨水源（注入前 $m$ 个瓶子的 $m$ 种不同颜色墨水，或来自其他非空瓶子的墨水）获取墨水，且这些源的墨水颜色不全相同，则称 B 为“混合器”（mixer）。
• 非混合器的非空瓶子，其墨水颜色与它的所有源的墨水颜色相同。
• 混合器瓶子包含一种全新的颜色，该颜色与注入前 $m$ 个瓶子的墨水颜色均不同。此外，不同的混合器瓶子包含的颜色也互不相同。

你需要求出在平衡状态下，瓶子中可能存在的最少不同墨水颜色数量。

输入格式

输入包含三行整数 $n, m, k$ ($1 \le m \le n \le 100,000$, $1 \le k \le 500,000$)，其中 $n$ 是墨水瓶的数量，$m$ 是注入了唯一墨水的瓶子数量，$k$ 是软管的数量。墨水瓶编号从 $1$ 到 $n$。接下来的 $k$ 行中，第 $i$ 行包含两个非负整数 $f_i$ 和 $t_i$，表示第 $i$ 条软管将第 $f_i$ 个瓶子的墨水输送到第 $t_i$ 个瓶子。多条软管可能连接同一对瓶子。

输出格式

输出一行，包含平衡状态下瓶子中可能存在的最少不同墨水颜色数量。

样例

样例输入 1

4 2 3
1 3
2 3
2 4

样例输出 1

3

样例输入 2

4 2 4
1 3
1 4
2 3
2 4

样例输出 2

4

样例输入 3

4 2 5
1 2
2 1
1 3
3 4
4 4

样例输出 3

2

样例输入 4

4 2 1
3 4

样例输出 4

2