Shortest Path in Grid with Wormholes

You are given an N × N grid. Each cell of the grid is either an open cell '.', a wall '#' or a wormhole represented by an alphabetical character (a-z or A-Z). You start at the top-left cell (0,0) and want to reach the bottom-right cell (N-1,N-1).

You can move one step at a time in the four cardinal directions (up, down, left, right) provided that the destination cell is not a wall.

If you step on a cell with an alphabetic character, it represents a wormhole. All cells with the same letter form a teleportation network: if you step on a wormhole cell, you can instantly move to any other cell with the same letter at no additional step cost. However, once used from a letter, the wormhole connection is no longer available.

Your task is to compute the minimum number of steps required to move from the start cell to the destination cell. If it is impossible to reach the destination, output -1.

The movement rules can be formally described by the following equation for the cost when using a wormhole:

\[ \text{cost}(i \to j) = \begin{cases} \text{cost}(i) + 1 & \text{if moving normally}, \\ \text{cost}(i) & \text{if teleporting via a wormhole}. \end{cases} \]

inputFormat

The input is given via standard input with the following format:

N
row_1
row_2
... 
row_N

Here, N (1 ≤ N ≤ 110) is the size of the grid, and each row_i is a string of exactly N characters representing the i-th row of the grid. The grid contains only the characters ., #, and alphabetic characters which denote wormholes.

outputFormat

Output a single integer to standard output, representing the minimum number of steps required to reach the bottom-right cell from the top-left cell. If reaching the destination is impossible, output -1.

## sample

4
....
.#a.
##a#
....

6