Migrated from Lutece 2840 Fatdog Wants to Buy Games

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There are $n$ students in a game club. The number of different games they have played together does not add up to $m$. In this club, every two students can be good friends in the following patterns.

1. If student $X$ has played a game that is also had played by student $Y$, the two students $X$ and $Y$ can become good friends.
2. If student $X$ is one of $Y$'s friends, meanwhile students $Z$ is also a good friend of $Y$'s, the two students $X$ and $Z$ can become good friends.

Fatdog already knows which games each student has played. He wishes any two students in the club to be friends. He decides to buy some games as gifts for some of the students in the club. After he bought a game $G$ as a gift for student $X$, in that case, we can assume that $X$ had played the game $G$.

But Fatdog is so poor, so he wants to buy the minimum number of games to achieve his wish. Could you please help Fatdog calculate the minimum number of games he needs to buy?

Input

The first line contains three integers $n,m,k\ (2\le n\le 10^5,1\le m\le 10^5,0\le k\le 10^5)$.

For the following $k$ lines, each line contains two integers $u,v\ (1\leq u\leq n,\ 1\leq v \leq m)$, representing that before Fatdog buys any game, the $u$-th student had played the $v$-th game.

Output

One integer, which stands for the minimum number of games Fatdog needs to buy.

Samples

3 3 2
2 3
3 1

2

Resources

The 18th UESTC Programming Contest Preliminary