On the Grid

이제 막 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을 출력한다.