Moo Game

The cows have come up with an innovative game called Moo – arguably the least creative name ever chosen! The game is played on an \(N \times N\) grid of square cells. During the game, a cow can claim a cell by shouting "Moo!" and writing her numeric ID in that cell.

At the end of the game, every cell on the board contains a number. A region is defined as a set of cells with the same number that are connected via their four neighbors (up, down, left, right). A single cow wins if she creates a region that is at least as large as every other cow’s region.

The cows also enjoy team play. In a two-cow team, the team’s region is defined as a contiguous set of cells containing numbers from either of the two cows, but the region is valid only if it includes at least one cell from each cow. Given the final state of the board, your task is to determine:

1. The maximum size of any region formed by a single cow.
2. The maximum size of any valid region formed by a two-cow team.

Note: Regions are connected if cells share an edge. Diagonals are not considered adjacent. All formulas are rendered in \(\LaTeX\) (e.g. \(N \times N\)).

inputFormat

The first line of input contains a single integer \(N\) representing the size of the board. The next \(N\) lines each contain \(N\) integers representing the cow ID written in each cell.

For example:

3
1 1 2
1 2 2
3 3 2

outputFormat

Output two integers separated by a space. The first integer is the size of the largest region created by a single cow, and the second integer is the size of the largest valid region created by a two-cow team.

For the sample input above, the output should be:

4 7

sample

3
1 1 2
1 2 2
3 3 2

4 7