SCUSA Region ACM Balloon Logo ICPC Masthead
2008 South Central USA Regional Programming Contest

The Sidewinder Sleeps Tonite

Introduction:

Slitherlink is a type of logic puzzle made popular by Nikoli, the same Japanese puzzle company that has made Sudoku popular the world over. Like most good logic puzzles, it has a set of very basic rules that can nonetheless result in devilishly difficult (and delightful!) puzzling experiences.

The rules of Slitherlink are as follows:

Unsolved 5x5 Puzzle Solved 5x5 Puzzle

Given a supposedly solved Slitherlink puzzle, your task will be to determine whether or not it is indeed legitimately solved.

Input:

Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of the following components:

Note that all Slitherlink puzzles will be fully represented; that is, there is no internal whitespace on a given line to represent empty cells or adjacencies.

Output:

For each data set, print "VALID" if the solution is a valid solution to the given Slitherlink, or "INVALID" if the solution is not valid.

Sample Input:

2
5 5
#-#-#-#-#-#
|?.?.?.1.3|
#.#-#-#.#-#
|?|?.?|?|?.
#-#.#.#.#-#
.2.0.2|?.?|
#-#.#-#.#-#
|?|3|?.?|2.
#.#-#.#-#.#
|?.?.2|?.0.
#-#-#-#.#.#
5 5
#-#-#-#-#-#
|?|?.?.1.3|
#.#-#-#.#-#
|?|?.?|?|?.
#-#.#.#.#-#
.2.0.2|?.?|
#-#.#-#.#-#
|?|3|?.?|2.
#.#-#.#-#.#
|?.?.2|?.0.
#-#-#-#-#.#

Sample Output:

VALID
INVALID