题目描述

译自 BalticOI 2012 Day1 T3. Peaks

住在岛上的一位登山者已经爬到了一座山的山顶，他现在渴望去爬一座更高的山峰。

这座岛上每一个点的海拔都为正（海平面的海拔为 $0$），如果登山者已经到达了一座海拔为 $E_i$ 的山峰，那他会尝试去一座海拔 $E_j$ 的山峰（其中 $E_j \geq E_i$）。因为他在山顶，所以为了前往其他山峰，他必须先下山。因为下山没有上山那么有趣，登山者希望最大化他从当前位置到目的地的路径上最低点的海拔。

举个例子，如果岛的轮廓如下所示，登山者位于海拔为 $E_4$ 的山峰上，他可以前往海拔为 $E_5,E_6,E_7$ 的山峰。从 $E_4$ 到 $E_7$，他到达的最低海拔是 $E_2$；而从 $E_4$ 到 $E_5$ 或 $E_6$，他到达的最低海拔是 $E_1$。如果他从 $E_5$ 出发，他到更高的山峰所经过的最低海拔是 $E_3$（前往 $E_6$ 的时候），如果他从 $E_6$ 出发，他到更高的山峰所经过的最低海拔是 $E_1$。

岛屿地图是一个 $N \times M$ 的矩阵，每个格子上的数字描述了这个格子对应区域的海拔。两个格子是相邻的，当且仅当这两个格子有至少一个公共点。这意味着，任何一个不在地图边缘的格子都有 $8$ 个格子与之相邻。路径是一个序列，序列中连续的两个格子是相邻的。一个平坦的区域是一组能互相到达的海拔相同的点的极大集合。山峰是一个平坦的区域，且其不与任何海拔更高的平坦区域相邻。

你的任务是，读入这个岛屿的地图，找出这座岛屿上的所有山峰，并为每一座山峰，找到前往比其高度更高的山峰所需经过的最低点的海拔的最大值。特别地，对于岛上的最高峰（这座岛上不存在比其更高的山峰），登山者将离开这座岛，去寻找更高的山峰，因此，这种情况下，经过的最低点的海拔将会是 $0$（即海平面）。

输入格式

第一行两个整数 $N,M$，分别代表地图的长和宽。

接下来 $N$ 行，每行 $M$ 个整数 $E_{i,j}$，描述了 $(i,j)$ 的海拔。

输出格式

第一行一个整数 $P$，代表岛上的山峰数。

接下来 $P$ 行，每行两个整数，分别代表某座山峰的海拔，以及从该山峰出发到达更高的山峰所需经过的最低点的海拔的最大值。

山峰信息应该按海拔高度降序排列，若存在两座海拔相同的山峰，则按从该山峰出发到达更高的山峰所需经过的最低点的海拔的最大值的降序排列。

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

5 3
16 14 16
14 14 15
12 17 16
12 13 10
16 11 16

5
17 0
16 15
16 14
16 13
16 13

数据范围与提示

• 对于 $15\%$ 的数据：$N \leq 2$ 或 $M \leq 2$；
• 对于 $50\%$ 的数据：$P \leq 500$；
• 对于 $80\%$ 的数据：$P \leq 5000$；
• 对于 $100\%$ 的数据：$1 \leq N,M \leq 2000$，$N \times M \leq 10^5$，$1 \leq E_{i,j} \leq 10^6$。