DR = [0, 1, -1, 0, 0]
DC = [0, 0, 0, 1, -1]
tiles = None
move_rows = []
move_cols = []
h = -1
w = -1
def check(r1, c1, r2, c2):
if r1 < 0 or h <= r1 or c1 < 0 or w <= c1:
return False
if r2 < 0 or h <= r2 or c2 < 0 or w <= c2:
return False
if r1 == r2 and c1 == c2:
return True
if r1 != r2 and c1 != c2:
return False
len = abs(r1 - r2) + abs(c1 - c2)
dr = (r2 - r1) // len
dc = (c2 - c1) // len
while r1 != r2 or c1 != c2:
if tiles[r1][c1] < 0:
return False
r1 += dr
c1 += dc
return tiles[r1][c1] >= 0
def shift(r1, c1, r2, c2):
global move_rows
global move_cols
if r1 == r2 and c1 == c2:
return
len = abs(r1 - r2) + abs(c1 - c2)
dr = (r2 - r1) // len
dc = (c2 - c1) // len
tile = tiles[r1][c1]
while r1 != r2 or c1 != c2:
tiles[r1][c1] = tiles[r1 + dr][c1 + dc]
r1 += dr
c1 += dc
tiles[r1][c1] = tile
move_rows += [r2]
move_cols += [c2]
def slide(r1, c1, r2, c2):
for i in range(5):
for j in range(5):
rs = r1 + DR[i]
cs = c1 + DC[i]
rf = r2 + DR[j]
cf = c2 + DC[j]
rm = [rs, rf]
cm = [cf, cs]
way = 0
while way < 2 and (not check(rs, cs, rm[way], cm[way]) or not check(rm[way], cm[way], rf, cf)):
way += 1
if way < 2:
shift(r1, c1, rs, cs)
shift(rs, cs, rm[way], cm[way])
shift(rm[way], cm[way], rf, cf)
shift(rf, cf, r2, c2)
return
def move4(r1, c1, r2, c2):
if r1 == r2 and c1 == c2:
return
rs = -1
cs = -1
for i in range(h):
for j in range(w):
if tiles[i][j] == 0:
rs = i
cs = j
len = abs(r1 - r2) + abs(c1 - c2)
dr = (r2 - r1) // len
dc = (c2 - c1) // len
while r1 != r2 or c1 != c2:
tiles[r1][c1] = -tiles[r1][c1]
slide(rs, cs, r1 + dr, c1 + dc)
tiles[r1][c1] = -tiles[r1][c1]
shift(r1 + dr, c1 + dc, r1, c1)
rs = r1
cs = c1
r1 += dr
c1 += dc
def move3(label, row, col):
rs = -1
cs = -1
for i in range(h):
for j in range(w):
if tiles[i][j] == label:
rs = i
cs = j
rm = [rs, row]
cm = [col, cs]
way = 0
while way < 2 and (not check(rs, cs, rm[way], cm[way]) or not check(rm[way], cm[way], row, col)):
way += 1
move4(rs, cs, rm[way], cm[way])
move4(rm[way], cm[way], row, col)
def build():
global move_rows
global move_cols
move_rows = []
move_cols = []
for i in range(h - 2):
for j in range(w - 2):
move3(i * w + j + 1, i, j)
tiles[i][j] = -tiles[i][j]
move3(i * w + w - 1, i, w - 1)
if tiles[i][w-2] == 0:
shift(i, w - 2, i + 1, w - 2)
if tiles[i][w-2] == i * w + w:
move4(i, w - 2, i + 1, w - 2)
shift(i, w - 2, i, w - 1)
shift(i, w - 1, i + 2, w - 1)
shift(i + 2, w - 1, i + 2, w - 2)
shift(i + 2, w - 2, i + 1, w - 2)
shift(i + 1, w - 2, i + 1, w - 1)
shift(i + 1, w - 1, i, w - 1)
shift(i, w - 1, i, w - 2)
shift(i, w - 2, i + 1, w - 2)
move3(i*w + w, i + 1, w - 1)
tiles[i + 1][w - 1] = -tiles[i + 1][w - 1]
move4(i, w - 1, i, w - 2)
tiles[i + 1][w - 1] = -tiles[i + 1][w - 1]
shift(i, w - 1, i + 1, w - 1)
tiles[i][w - 2] = -tiles[i][w - 2]
tiles[i][w - 1] = -tiles[i][w - 1]
for j in range(w - 2):
move3((h - 2)*w + j + 1, h - 1, j);
if tiles[h - 2][j] == 0:
shift(h - 2, j, h - 2, j + 1);
if tiles[h - 2][j] == (h - 1)*w + j + 1:
move4(h - 2, j, h - 2, j + 1)
shift(h - 2, j, h - 1, j)
shift(h - 1, j, h - 1, j + 2)
shift(h - 1, j + 2, h - 2, j + 2)
shift(h - 2, j + 2, h - 2, j + 1)
shift(h - 2, j + 1, h - 1, j + 1)
shift(h - 1, j + 1, h - 1, j)
shift(h - 1, j, h - 2, j)
shift(h - 2, j, h - 2, j + 1)
move3((h - 1)*w + j + 1, h - 1, j + 1)
tiles[h - 1][j + 1] = -tiles[h - 1][j + 1]
move4(h - 1, j, h - 2, j)
tiles[h - 1][j + 1] = -tiles[h - 1][j + 1]
shift(h - 1, j, h - 1, j + 1)
tiles[h - 2][j] = -tiles[h - 2][j]
tiles[h - 1][j] = -tiles[h - 1][j]
rows = [h - 1, h - 2, h - 2, h - 1]
cols = [w - 1, w - 1, w - 2, w - 2]
for i in range(4):
cnt = 0
for j in range(4):
if tiles[rows[j]][cols[j]] == rows[j] * w + cols[j] + 1:
cnt += 1
if cnt == 3:
return True
for j in range(4):
if tiles[rows[j]][cols[j]] == 0:
slide(rows[j], cols[j], rows[(j + 1) % 4], cols[(j + 1) % 4])
return False
def solve():
global h
global w
global tiles
h, w = [int(x) for x in input().split()]
puzzle = []
for i in range(h):
puzzle += [input().strip()]
rows = []
cols = []
chars = []
for _c in range(26):
c = chr(ord('a') + _c)
for i in range(h):
for j in range(w):
if puzzle[i][j] == c:
rows += [i]
cols += [j]
chars += [c]
for i in range(2):
tiles = []
for j in range(h):
tiles += [[0] * w]
for j in range(len(chars)):
tiles[rows[j]][cols[j]] = j + 1
if build():
return True
for j in range(1, len(chars)):
if chars[j] == chars[j - 1]:
rows[j], rows[j-1] = rows[j-1], rows[j]
cols[j], cols[j-1] = cols[j-1], cols[j]
break
return False
solve()
print(len(move_rows))
for x, y in zip(move_rows, move_cols):
print(f'{x + 1} {y + 1}')
