MAKEMAZE - VALIDATE THE MAZE

There are many algorithms to generate maze. (http://en.wikipedia.org/wiki/Maze_generation_algorithm). After generating the maze we’ve to validate whether it’s a valid maze or not. A valid maze has exactly one entry point and exactly one exit point (exactly 2 openings in the edges) and there must be at least one path from the entry point to exit point.

Given a maze, just find whether the maze is "valid" or "invalid".

Input

The first line consists of an integer t, the number of test cases. Then for each test case, the first line consists of two integers m and n, the number of rows and columns in the maze. Then contains the description of the matrix M of order mxn. M[i][j]=# represents a wall and M[i][j]='.' represents a space.

Output

For each test case find whether the maze is "valid" or "invalid".

Constraints

1<=t<=10000

1<=m<=20

1<=n<=20

Example

Input:
6
4 4
####
#...
#.##
#.##
5 5
#.###
#..##
##..#
#.#.#
###.#
1 1
.
5 1
#
#
.
.
#
2 2
#.
.#
3 4
#..#
#.##
#.##

Output:
valid
valid
invalid
valid
invalid
invalid

Added by:cegprakash
Date:2012-05-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2013-12-12 23:21:48 shiva_hellgeek
the problem is really nice.
but i don't know why a space is given between the characters whereas actually there is no space...
2013-12-12 23:21:48 mudiyala
Loved solving it ~~!!! :D Wonderful testcases :)
2013-12-12 23:21:48 Kumar Mrinal
piece of cake :D
2013-12-12 23:21:48 god_father
easy one ;got Ac in first Attempt..
2013-12-12 23:21:48 ravi teja
plz check submission id: 839598
checked for given as well as lot of other test cases, giving WA
2013-12-12 23:21:48 Aditya Pande
m getting WA for my submission
7361888 but i tried a lot of test cases myself and it gave the correct answer everytime
@cegprakash please tell me for which tricky case does my submission fail
2013-12-12 23:21:48 gabber
is this valid?
1 2
..

cegprakash: Yes

Last edit: 2012-11-25 15:38:54
2013-12-12 23:21:48 Sardar Khan
simple graph problem
2013-12-12 23:21:48 npsabari
easy one!
2013-12-12 23:21:48 Aradhya
goodness me :D in input there is a apace btw two characters.. but actually it is nt so.. got too many wrng answers for that misconception.. be careful :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.