Distant Cows

Farmer John's farm is arranged as an \(N \times N\) square grid of fields with a fence surrounding the farm. Certain pairs of adjacent fields (north-south or east-west) are separated by roads.

There are \(K\) cows occupying different fields. The cows can move between adjacent fields as long as no road separates those fields. Two cows are considered distant if in order for one to reach the other, at least one road must be crossed.

Your task is to count the number of distant pairs of cows. A useful formula is that the number of unordered pairs from \(x\) items is \(\binom{x}{2} = \frac{x(x-1)}{2}\). To solve the problem, you can identify connected components of the farm that are reachable without crossing any roads using a flood fill (or DFS/BFS) algorithm. Then, if a connected component contains \(c\) cows, they contribute \(\binom{c}{2}\) pairs which are not distant. Subtracting the sum over components from the total \(\binom{K}{2}\) gives the answer.

inputFormat

The first line contains three integers \(N\), \(K\) and \(R\): the grid size, the number of cows, and the number of roads respectively. \(2 \le N \le 100\) and \(1 \le K \le 100, K \le N^2\).

Then follow \(R\) lines. Each of these contains four integers \(r_1, c_1, r_2, c_2\) indicating that there is a road between the adjacent fields \((r_1, c_1)\) and \((r_2, c_2)\). Fields are 1-indexed and adjacent means north-south or east-west.

Finally, there are \(K\) lines, each containing two integers \(r\) and \(c\) representing the row and column of a cow.

outputFormat

Output a single integer: the number of distant pairs of cows.

sample

3 3 3
1 1 1 2
2 1 2 2
3 1 3 2
1 1
2 2
3 3

2