Minimum Initial Ignitions for Grid Lights

In an n × m grid, every cell contains an off light. In k of these cells, fuel is placed. A light can be ignited in two ways:

• Direct ignition: If the cell has fuel, you may choose to ignite it initially (igniting one fuel per cell, even if the cell contains multiple fuel sources).
• Automatic propagation: The lights exhibit a peculiar behavior. Consider any rectangle in the grid defined by cells \( (x,y),\ (x+a,y),\ (x,y+b),\ (x+a,y+b) \) where \(a,b\) are positive integers and the indices obey \(1 \le x < x+a \le n,\; 1 \le y < y+b \le m\). If any three of the four cells have their lights lit, then the remaining one will automatically be lit.

The grid is indexed by \((i,j)\), where \(i\) is the row number counting from the bottom up and \(j\) is the column number from left to right. In particular, the cell \((1,1)\) is the bottom‐left cell and \((1,m)\) is the bottom‐right cell.

Your task is to choose a set of fuel‐cells to ignite initially (you cannot ignite cells that do not have fuel) so that, after the propagation process, both cell \((1,1)\) and cell \((1,m)\) are lit. Determine the minimum number of initial ignitions required or report that it is impossible to light one (or both) of the target cells.

Observation and Explanation:

The process has an underlying combinatorial structure. Notice that the automatic propagation rule effectively “completes” rectangles. In fact, if you have lit cells at \((r, c)\) and \((r, c')\) in some row and a lit cell in another row at one of these columns, then the corresponding cell in the other row at the other column will eventually be lit. In other words, if you consider the bipartite graph where one part is the set of rows \(\{1,2,\dots,n\}\) and the other part is the set of columns \(\{1,2,\dots,m\}\), and add an edge between row \(r\) and column \(c\) whenever the fuel cell \((r,c)\) is chosen for direct ignition, then the propagation rule will eventually light all cells at intersections of rows and columns within each connected component.

Thus, the problem reduces to selecting a set of available edges (fuel cells) with minimum size such that in the resulting bipartite graph the following three vertices lie in the same connected component:

• Row 1 (corresponding to the target row for both cells)
• Column 1 (target for cell \((1,1)\))
• Column m (target for cell \((1,m)\))

This is essentially a minimum Steiner tree problem on a bipartite graph with three terminals. Let us denote:

• \(a\): vertex corresponding to Row 1
• \(b\): vertex corresponding to Column 1
• \(c\): vertex corresponding to Column m

You are given n, m and k (the number of fuel cells), followed by k lines each containing two positive integers \(i\) and \(j\) (\(1 \le i \le n, \; 1 \le j \le m\)) indicating that cell \((i,j)\) has fuel. Determine the minimum number of fuel cells to ignite initially so that the bipartite graph (with row vertices numbered 1 to n and column vertices numbered n+1 to n+m, where column \(j\) corresponds to vertex \(n+j\)) has Row 1, Column 1 (vertex \(n+1\)), and Column m (vertex \(n+m\)) in the same connected component. If it is impossible, output -1.

inputFormat

The first line contains three integers n m k — the number of rows, columns, and the number of fuel cells, respectively.

Each of the next k lines contains two integers i j indicating that cell \((i,j)\) (with \(i\) counting from the bottom up and \(j\) from left to right) has fuel.

outputFormat

Output a single integer — the minimum number of initial ignitions required. If it is impossible to eventually light both cells \((1,1)\) and \((1,m)\), output -1.

sample

3 3 3
1 1
1 3
2 2

2