Counting Connected Plants in a Plantation

A plantation on planet w is divided into an \( m \times n \) grid of cells (with \( m \) rows in the east-west direction and \( n \) columns in the north-south direction). Each cell contains a grafted plant. Some plants become connected through their roots if the roots extend in the north-south or east-west direction and meet a neighboring cell’s plant.

You are given the positions of pairs of adjacent cells that are connected by roots. Two cells are considered connected if there is a path between them via connected adjacent cells. Your task is to determine the total number of independent (i.e. not connected by any root) plants in the plantation.

Note: The connections occur only between adjacent cells (either horizontally or vertically) and the cell indices are considered 1-indexed.

inputFormat

The first line contains two integers \( m \) and \( n \) representing the number of rows and columns of the grid, respectively.

The second line contains an integer \( k \), the number of connections between adjacent cells.

Each of the following \( k \) lines contains four space-separated integers \( x_1, y_1, x_2, y_2 \) indicating that the cell at row \( x_1 \) and column \( y_1 \) is connected to the cell at row \( x_2 \) and column \( y_2 \). It is guaranteed that the two cells are adjacent (either horizontally or vertically).

outputFormat

Output a single integer representing the number of independent (connected component) plants in the grid.

sample

3 3
2
1 1 1 2
2 2 3 2

7