Chess from "Harry Potter"#3296
A lot of people were impressed by the huge chess scene in a movie about Harry Potter. It made chess games feel grand and magical. In this story, the chess pieces sometimes play among themselves when they have free time and get bored of waiting for players.
However, there is a small problem: whenever a piece is captured, it does not leave the board immediately, blocking the way for the remaining pieces. To help clear the board, they ask a fairy with a magic vacuum cleaner to remove the captured pieces from their squares. The vacuum cleaner is quite bulky, even though it is magic, and it can only move through empty squares that share a side.
To make the cleaning as fast as possible, the fairy asks you to determine the minimum number of squares she must go through (including the square with the captured piece) to reach the square with the captured piece. Initially, the fairy is outside the board.
The first line contains the number of pieces (2 \leq n \leq 31) currently on the board, and the coordinates of the square where the capture occurred. The next lines contain the coordinates of the pieces. The first character is the file (from to ), the second is the rank (from to ).
Print the minimum number of cells, including the square with the captured piece, which the fairy must pass through. If it is impossible to reach the target square, output .
Example 1