일관된 글자 경로

논리 도시의 공원은 $N \times N$ 격자다 ($2 \le N \le 100$). 각 칸에는 알파벳 첫 10글자 abcdefghij 중 하나가 소문자나 대문자로 적혀 있다. 이 도시 사람들은 공원을 건널 때 일관된 경로만 따른다. 소문자 c가 적힌 칸을 지났다면 그 뒤로 대문자 C가 적힌 칸은 지나지 않는다.

일관된 경로는 다음 두 조건을 만족하는 칸의 수열이다.

• 수열에서 이웃한 두 칸은 변을 맞대고 있다. 이동은 상하좌우로만 한다.
• 어떤 글자도 수열에서 소문자와 대문자로 함께 나타나지 않는다. 각 글자는 수열에 아예 없거나, 소문자로만 나타나거나, 대문자로만 나타난다.

경로의 길이는 수열에 들어 있는 칸의 개수이고, 시작 칸과 끝 칸도 센다.

아래 그림에서 왼쪽은 공원이고, 오른쪽은 그 공원에서 길이가 13인 일관된 경로 하나를 나타낸다. 경로에 속한 칸은 글자를 그대로 두고 나머지 칸은 점으로 바꿨다.

DdaAaA D.....
CBAcca C.....
eEaeeE e.....
bBbabB b.bab.
DbDdDc DbD.D.
fFaAaC ....aC

왼쪽 위 칸 $(1, 1)$에서 오른쪽 아래 칸 $(N, N)$까지 가는 가장 짧은 일관된 경로의 길이를 구하라.

첫째 줄에 공원의 크기 $N$이 주어진다 ($2 \le N \le 100$). 다음 $N$개 줄에 각각 길이 $N$인 문자열이 주어진다. $i$번째 문자열의 $j$번째 글자는 칸 $(i, j)$에 적힌 글자이고, abcdefghij와 ABCDEFGHIJ 중 하나다.

$(1, 1)$에서 $(N, N)$까지 가는 가장 짧은 일관된 경로의 길이를 한 줄에 출력한다. 그런 경로가 없으면 -1을 출력한다.