Slitherlink
The puzzle game Slitherlink is played on a grid. Each cell of the grid contains either a space or an integer from 0 to 3. The goal is to draw in some grid lines con necting vertically or horizonally adjacent points on the grid subject to the following constraints:
 If a grid cell is numbered k then ex actly k out of the 4 adjacent grid lines are drawn.
 The grid lines form a single loop that does not cross itself.
Determining if a given instance of a
Slitherlink puzzle can be completed or
not is NPcomplete which means nobody
knows of an efficient algorithm to solve
the problem for large grids. Your task is
simpler. Given an instance of a Slither
link puzzle and a proposed solution, you
are to check that the solution indeed satisfies the constraints for that puzzle.
For example, the first sample input is not valid since there are 2 grid lines drawn adjacent to a cell numbered 1. The second, third, and fourth samples are invalid since the grid lines do not form a single loop. However, the fifth sample is valid.
Input
The first integer denotes the number of test cases to follow. Each test case is specified by a line containing two positive integers R and C (both at most 50) followed by a grid of 2R + 1 rows of 2C + 1 characters. The contents of row r and column c (counting from 1) are as follows:
 if both r and c are odd then the character is a ‘+’ indicating a grid point
 if both r and c are even then the character is either a space or one of 0, 1, 2, or 3 indicating the
contents of the corresponding grid space
 if r is odd and c is even then the character is either a space or ‘’ indicating a drawn horizontal grid line
 if r is even and c is odd then the character is either a space or ‘’ indicating a drawn vertical grid line
You can assume all inputs are wellformed descriptions of a Slitherlink puzzle and a proposed solution. A blank line also precedes each test case.
2/3 Output
The output for each test case is a single line containing either ‘Valid’ or ‘Invalid’, depending on whether the proposed solution is valid or not.
Sample Input
5
33

++ +
1 2 ++ ++ 1 +++ +
1 3 + + ++
23
++ ++ 3 3 ++++ 3 3 ++ ++
22 +++ 33 +++ 33 +++
22

++
2 
+++
 2
++ +
34

+++ +
 2 ++ + ++ 30 3 ++ +++
1 + ++ + +
Sample Output
Invalid
Invalid
3/3
Invalid
Invalid
Valid