Flea Disconnection

Two kings, the Flea King and the Cricket King, are playing a game. They arrange their troops on an $n\times m$ grid. In the grid, exactly $c$ cells ($0\le c\le n\times m$) initially contain a cricket, and every other cell contains a flea. We say that two fleas in cells sharing a common edge are adjacent. Moreover, two fleas are considered connected if and only if they are adjacent or there is some other flea that is connected to both (i.e. connectivity is defined transitively).

The Cricket King wants to replace some of the fleas (possibly zero, one, or more) with crickets. After the replacement, there must exist at least two fleas that are not connected (note that after replacement, there must be at least two fleas remaining).

For example, consider a grid with $n=4$, $m=4$, and $c=2$. In the illustration, initially there are two crickets and the remaining cells have fleas. The Cricket King can achieve his goal by replacing the flea in cell $(2,2)$ and the flea in cell $(3,3)$ with crickets. It can be shown that no solution exists that uses fewer than two replacements, though there may be other valid solutions replacing two fleas.

Your task is to determine whether the Cricket King's goal can be achieved, and if so, find the minimum number of flea replacements needed.

inputFormat

The input begins with three integers $n$, $m$, and $c$ ($1\le n,m\le 50$, $0\le c\le n\times m$), representing the number of rows, number of columns, and the number of cells that initially contain a cricket, respectively. The next $c$ lines each contain two integers $r$ and $c$ ($1\le r\le n$, $1\le c\le m$), indicating the row and column indices of a cell that initially contains a cricket. Cells not listed in these $c$ lines contain a flea.

outputFormat

Output a single integer: the minimum number of flea replacements (i.e. turning a flea cell into a cricket) required so that the remaining fleas are not all connected (in other words, there exist at least two fleas which are not connected). If it is impossible to achieve the goal, output -1.

sample

4 4 2
2 2
3 3

2