/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
縦 H 行横 W 列のマス目があり、上から i 行目、左から j 列目のマスには数 A_{i,j} が書かれています。
A_{i,j} はそれぞれ 1 以上 HW 以下の整数であり相異なります。
1\leq x < y \leq HW を満たす整数の組 (x,y) であって、x が書かれているマスと y が書かれているマスが隣り合っているようなものを全て求めてください。
なお、2 つのマスが隣り合っているとは、2 つのマスが辺を共有していることを指します。
制約
- 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}
出力
1\leq x < y \leq HW を満たす整数の組 (x,y) であって、x が書かれているマスと y が書かれているマスが隣り合っているようなものの個数を K とする。
K 行出力せよ。i 行目には、そのような組のうち辞書順で i 番目のものについて、x,y を空白区切りで出力せよ。
入力例 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
Problem Statement
There is a grid with H horizontal rows and W vertical columns. The square at the i-th row from the top and j-th column from the left has a number A_{i,j} written on it.
A_{i,j} are distinct integers between 1 and HW.
Find all the integer pairs (x,y) satisfying 1\leq x < y \leq HW such that the square with x written on it is adjacent to the one with y.
A square is said to be adjacent to another if these two squares share a side.
Constraints
- 1 \leq H,W
- 2 \leq H \times W \leq 2\times 10^5
- 1 \leq A_{i,j} \leq H \times W
- H and W are integers.
- A_{i,j} are distinct integers.
Input
The input is given from Standard Input in the following format:
H W
A_{1,1} \ldots A_{1,W}
\vdots
A_{H,1} \ldots A_{H,W}
Output
Let K be the number of integer pairs (x,y) satisfying 1\leq x < y \leq HW such that the square with x written on it is adjacent to the one with y.
Print K lines. The i-th line should contain x and y for the i-th lexicographically smallest such pair, separated by a space.
Sample Input 1
2 3 2 3 4 1 6 5
Sample Output 1
1 2 1 6 2 3 3 4 3 6 4 5 5 6
The square with 1 written on it is adjacent to the one with 2.
Sample Input 2
3 1 1 2 3
Sample Output 2
1 2 2 3