Avoiding Food Waste

Interview

Time limit2sMemory limit128 MB

Summary

Given a grid marked with food waste cells, find the size of the largest 4-directionally connected component using BFS/DFS or union-find.

Level: Easy3 of 10
Topics: BFS, DFS, Union-find
Solved: No attempts yet

Problem

On the eighth floor of Koresco Condominium, food waste has been dropped along a hallway. Food cells adjacent vertically or horizontally belong to the same connected lump.

A teacher wants to avoid at least the largest lump while walking through the hallway. Given the coordinates of the food cells, find the size of the largest lump.

Input

The first line contains the hallway height N (1 ≤ N ≤ 100), width M (1 ≤ M ≤ 100), and the number of food cells K (1 ≤ K ≤ N×M). Each of the next K lines contains the coordinate (r, c) of one food cell.

The row r is counted from the top, and the column c is counted from the left. No coordinate is given more than once.

Output

Print the size of the largest group of food cells connected vertically or horizontally.

Hint

# . . .
. # # .
# # . .

In the layout above, four food cells are connected vertically or horizontally, so the largest lump has size 4. Cells touching only diagonally are not connected.

Examples1

Example 1
Input
```
3 4 5
3 2
2 2
3 1
2 3
1 1
```
Expected output
```
4
```