격자 게임판

이제 막 C언어 수업을 마친 새내기 승희와 비니는 함수컵에 참가하기로 했다. 함수컵의 문제는 둘이 풀기에 매우 어려웠기 때문에, 두 사람은 심심풀이로 문제에 대해 이야기하기 시작했다.

승희: 이번 함수컵 문제는 왜 ABC순이 아닐까?

비니: ABC순이 아니면... 첫 글자에 숨어 있는 암호가 있는 거 아닐까?

승희: 흠, 'P, L, 2, Z, G, O, B, 1, T, O, A, 포'... 뭔가 있어 보이는데, 무언가 보이기도 하는 것 같고.

비니: 그냥 한글로 읽어보자. '플리즈(PL2Z) 고(GO) 비원(B1) 투(TO) 에이포(A포)'?!

승희: B1에서 A4로 가라는 게 무슨 뜻이지?

승희가 의문을 품은 채 옆을 돌아본 순간, $N \times N$ 크기 격자 보드게임이 눈앞에 나타났다. 보다시피 B행 1열에 말이 놓여 있고, A행 4열에 깃발이 놓여 있으며, 대각선 칸에는 물이 배치되어 있다. 물이 교묘하게 배치되어 있어서, 말을 상하좌우로 움직여 물을 지나지 않고는 깃발이 있는 곳에 갈 수 없다.

조금 뒤 승희와 비니는 게임판의 한 행이나 한 열을 통째로 들어낼 수 있다는 것을 깨닫고 게임판을 뒤섞기 시작했다. 승희는 게임판의 두 행을 들어내어 위치를 바꾼 뒤 다시 끼우고, 비니는 게임판의 두 열을 들어내어 위치를 바꾼다.

승희와 비니가 게임판을 몇 번 바꾸자 게임판은 아래와 같이 변했다.

이제 B1에 있는 말은 무난하게 A4로 갈 수 있다. B1의 말이 A4까지 가는 데 필요한 최소 이동 횟수는 5이다. 승희와 비니가 게임판을 바꿀 때마다 B1에서 A4로 가는 경로가 계속 바뀐다.

승희와 비니는 게임판을 바꿀 때마다 B1에서 A4까지 가는 가장 짧은 경로가 어떻게 바뀌는지 알아보려고 한다. 두 사람을 도와, 게임판을 바꿀 때마다 최단거리가 어떻게 변하는지 구하는 프로그램을 작성하여라. 편의상 Z행 이후의 행들은 AA행, AB행, …, AZ행, BA행, …, ZZ행, AAA행, AAB행, … 순으로 표기한다.

첫 번째 줄에 게임판의 크기 $N$과 게임판을 옮기는 횟수 $M$이 주어진다. ($4 \le N \le 100\,000$, $1 \le M \le 150\,000$)

두 번째 줄부터 $M$개의 줄에 게임판을 옮기는 정보가 주어진다. 1 r1 r2는 승희가 $r_1$행과 $r_2$행을 바꾼다는 뜻이며, $r_1$과 $r_2$는 알파벳 대문자로 주어진다. 2 c1 c2는 비니가 $c_1$열과 $c_2$열을 바꾼다는 뜻이며, $c_1$과 $c_2$는 숫자로 주어진다. $r_1, r_2, c_1, c_2$는 게임판의 크기에 맞게 주어지며, $r_1 \neq r_2$, $c_1 \neq c_2$를 만족한다.

참고로 100,000행은 알파벳으로 EQXD행이다.

$M$개의 줄에 걸쳐 게임판을 옮긴 후 B행 1열에서 A행 4열까지 가는 최단거리를 출력한다. B행 1열에서 A행 4열까지 갈 수 없다면 -1을 출력한다.