그래프 위의 하이킹

Hike on a Graph는 무향 그래프가 그려진 판 위에서 하는 게임입니다. 이 그래프는 완전 그래프이며 모든 정점에 자기 자신으로 가는 간선(루프)이 있습니다. 즉 임의의 두 위치 사이(그리고 한 위치에서 자기 자신으로)에는 정확히 하나의 간선이 있고, 모든 간선에는 색이 칠해져 있습니다.

세 명의 플레이어가 각자 말 하나씩을 가집니다. 게임을 시작할 때 세 말은 정해진 위치에 놓입니다. 자기 차례가 되면 플레이어는 자신의 말을 간선을 따라 다른 위치로 옮기는데, 다음 규칙을 지켜야 합니다. 말은 두 상대방의 말이 놓인 위치를 잇는 간선의 색과 같은 색의 간선을 따라서만 움직일 수 있습니다.

훗날 혼자서 하는 변형이 생겼습니다. 한 사람이 세 말을 모두 움직이되, 한 번에 하나씩 임의의 순서로 옮깁니다. 목표는 가능한 한 적은 이동 횟수로 세 말을 모두 같은 위치에 모으는 것입니다.

판과 시작 위치가 주어질 때, 세 말을 모두 한 위치에 모으는 데 필요한 최소 이동 횟수를 구하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 정수 $n$으로 시작합니다. $n = 0$인 줄이 나오면 입력이 끝나며, 그 외에는 $1 \le n \le 50$입니다.

이어서 세 정수 $p_1, p_2, p_3$가 주어지며, 이는 세 말의 시작 위치로 $1 \le p_i \le n$입니다.

그다음 색 행렬이 주어집니다. 공백으로 구분된 소문자 알파벳이 한 줄에 $n$개씩, 모두 $n$줄에 걸쳐 나옵니다. $i$행 $j$열의 값은 위치 $i$와 위치 $j$를 잇는 간선의 색입니다. 그래프가 무향이므로 이 행렬은 대칭입니다.

각 테스트 케이스마다 한 줄에, 세 말을 모두 같은 위치에 모으는 데 필요한 최소 이동 횟수를 출력합니다. 주어진 판과 시작 위치로는 불가능하다면 impossible을 출력합니다.