| Cube in the labirint |
There is a cube on a rectangular field of size X*Y, composed by squares of size 1x1. The sides of the cube fit in one square. The cube can move to horizontaly or verticaly to the next square by rolling over its edge. There are may be walls between squares. Cube can not move(role) through the walls. Also, cube can not leave the field.
You are to determinate the minimal number of moves, needed to take the cube from square (A, B) to square (C, D). In the end point, cube should be lay on the same side on which it was laid in the starting point.
The first line is the number of test cases, followed by a blank line.
The first line of each test case of input contains integers X and Y (2<=X, Y<=10), separated by one or more spaces. Second and third lines of each test cases contain integers A B and C D in the same format. There may be inforamtion about walls in the following strings.
After symbol "v", in a separate line, there will be a list of pairs of integers, describing vertical walls. Pair of integers N and M set a wall between squares N, M and N+1, M. Each pair on a separated line, with no blank lines in the middle.
Symbol "h", denotes horizontal walls. Pair of integers N and M set a wall between squares N, M and N, M+1.
Each test case will be separated by a single line.
Your programm should print the minimal number of moves for each test case. If target point can not be reached, print "No solution".
Print a blank line between the outputs for two consecutive test cases.
1 10 2 1 1 10 1 v 2 1 6 2 h 4 1
11