Description

There is an island of size $N \times M$, where each cell has a different elevation. Two cells are defined to be adjacent if the differences of their row and column coordinates are both at most $1$. A path is defined as a sequence of points such that every two consecutive points are adjacent. A flat region is the maximal connected set of points with the same elevation. A peak is a flat region that is not adjacent to any point with a higher elevation.

Given the elevation of every point on the island, you need to find, among all peaks on the island, the maximum value of: the highest possible elevation of the lowest point that must be passed when traveling from that peak to a higher peak.

Input Format

The first line contains two integers $N, M$, representing the height and width of the map.

The next $N$ lines each contain $M$ integers $E_{i,j}$, describing the elevation of $(i,j)$.

Output Format

The first line contains an integer $P$, representing the number of peaks on the island.

The next $P$ lines each contain two integers $h_0, h_1$, representing the elevation of a peak, and the maximum possible elevation of the lowest point that must be passed when starting from this peak to reach a higher peak.

The output should be sorted in descending order by $h_0$ as the primary key and $h_1$ as the secondary key. In particular, for the highest peak, $h_1 = 0$.

6 6
21 16 9 11 6 7
21 21 10 14 15 9
18 20 8 9 13 14
11 10 9 9 8 13
8 12 12 14 13 8
7 13 12 9 5 1

4
21 0
15 11
14 13
13 12

Hint

Sample Explanation.

As shown in the figure above, the circled ones are peaks. A path from the peak with elevation $15$ to another peak is highlighted in dark color.

Constraints.

• For $15\%$ of the testdata, $\min (N, M) \leq 2$.
• For $50\%$ of the testdata, $P \leq 500$.
• For $80\%$ of the testdata, $P \leq 5000$.
• For $100\%$ of the testdata, $1 \leq N, M \leq 2000$, $N \times M \leq 10^5$, $1 \leq E_{i,j} \leq 10^6$.

Notes.

Translated from BalticOI 2012 Day 1 T3. Peaks.

Translated by ChatGPT 5