Hike on a Graph

Hike on a Graph is played on a board showing an undirected graph. The graph is complete and has a loop at every vertex: between any two locations — and from a location to itself — there is exactly one edge, and every edge is coloured.

There are three players, each with one piece. At the start the three pieces sit on fixed locations. On a turn a player moves their own piece along an edge to another location, subject to one rule: the piece may only travel along edges whose colour matches the colour of the edge joining the two opponents' pieces.

A one-person variant appeared later: a single person moves all three pieces, one at a time and in any order. The goal is to gather all three pieces onto the same location using as few moves as possible.

Given a board and the starting positions, determine the smallest number of moves needed to bring all three pieces onto one location.

The input contains several test cases. Each test case begins with an integer $n$. A line containing $n = 0$ terminates the input; otherwise $1 \le n \le 50$.

Next come three integers $p_1, p_2, p_3$ with $1 \le p_i \le n$, the starting locations of the three pieces.

Then follows the colour matrix: $n$ rows of $n$ whitespace-separated lower-case letters. The entry in row $i$, column $j$ is the colour of the edge between locations $i$ and $j$. Because the graph is undirected, the matrix is symmetric.

For each test case, print a single line: the minimum number of moves needed to bring all three pieces onto the same location, or the word impossible if it cannot be done for the given board and starting positions.