← 返回题目列表

AtCoder · past202303_g

G. 相邻的方块

中文机器翻译题面 查看原题

问题陈述

有一个网格 H 水平行和 W 垂直列。 广场位于 i从顶部开始的第行和 j左起第 列有一个数字 上面写着 A_{i,j} 。
A_{i,j} 是之间不同的整数 1 和 HW.

查找所有整数对 (x,y) 满意 1\leq x < y \leq HW 这样的正方形 其上写的 x 与带有 y.

如果两个正方形共享一条边,则称该正方形与另一个正方形相邻。

约束

  • 1 \leq H,W
  • 2 \leq H \times W \leq 2\times 10^5
  • 1 \leq A_{i,j} \leq H \times W
  • H 和 W 是整数。
  • A_{i,j} 是不同的整数。

输入

输入由标准输入按以下格式给出:

H W
A_{1,1} \ldots A_{1,W}
\vdots
A_{H,1} \ldots A_{H,W}

输出

让 K 是整数对的数量 (x,y) 满意 1\leq x < y \leq HW 这样的正方形 其上写的 x 与带有 y.
打印 K 行。 的 i- 第行应包含 x 和 y 为 i- 按字典顺序最小的此类对,以空格分隔。


示例输入 1

2 3
2 3 4
1 6 5

示例输出 1

1 2
1 6
2 3
3 4
3 6
4 5
5 6

正方形 1 与带有 2.


示例输入 2

3 1
1
2
3

示例输出 2

1 2
2 3