HIKE  Hike on a Graph
"Hike on a Graph" is a game that is played on a board on which an undirected graph is drawn. The graph is complete and has all loops, i.e. for any two locations there is exactly one arrow between them. The arrows are coloured. There are three players, and each of them has a piece. At the beginning of the game, the three pieces are in fixed locations on the graph. In turn, the players may do a move. A move consists of moving one's own piece along an arrow to a new location on the board. The following constraint is imposed on this: the piece may only be moved along arrows of the same colour as the arrow between the two opponents' pieces.
In the sixties ("make love not war") a oneperson variant of the game emerged. In this variant one person moves all the three pieces, not necessarily one after the other, but of course only one at a time. Goal of this game is to get all pieces onto the same location, using as few moves as possible. Find out the smallest number of moves that is necessary to get all three pieces onto the same location, for a given board layout and starting positions.
Input
The input file contains several test cases. Each test case starts with the number n. Input is terminated by n=0. Otherwise, 1<=n<=50. Then follow three integers p_{1}, p_{2}, p_{3} with 1<=p_{i}<=n denoting the starting locations of the game pieces. The colours of the arrows are given next as a n×n matrix m of whitespaceseparated lowercase letters. The element m_{ij} denotes the colour of the arrow between the locations i and j. Since the graph is undirected, you can assume the matrix to be symmetrical.
Output
For each test case output on a single line the minimum number of moves required to get all three pieces onto the same location, or the word "impossible" if that is not possible for the given board and starting locations.
Example
Input: 3 1 2 3 r b r b b b r b r 2 1 2 2 y g g y 0 Output: 2 impossible
hide comments
youssef20:
20170416 11:13:51
we nide mor time


holmesherlock:
20170404 21:36:25
excellently framed problem,,, 

tni_mdixit:
20170301 19:22:02
Really good and easy problem! :) 

anirudhmenon89:
20160418 19:06:40
Excellent problem! Really enjoyed solving this.


Vaibhav Gosain:
20150604 12:15:13
there is some problem in the input files. It contains unnecessary whitespace. 

Deepak Gupta:
20140917 19:20:11
Remember, different edges from a single source can have same color 

Julian Waldby:
20131120 13:35:48
How can I tell what color the pieces are? 

Rohan Garg:
20130513 23:14:54
The time limit for Java must be increased ! Same solution in C++ passes but gets TLE in Java 

Adrian Kuegel:
20091015 11:45:33
after moving P2 to P1, the edge between P1 and P2 has color y, so the edge from 2 to 1 cannot be used for P3. 

Sai Ganesh:
20091004 10:42:17
why is it impossible for case2? why not move P2 and P3 to P1 in 2steps?? 
Added by:  Adrian Kuegel 
Date:  20050710 
Time limit:  0.869s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  University of Ulm Local Contest 2000 