SP11516 MAKEMAZE - VALIDATE THE MAZE

**MAZE MAKING** There are many algorithms to generate maze. ([http://en.wikipedia.org/wiki/Maze\_generation\_algorithm](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 atleast one path from the entry point to exit point.  Given a maze, just find whether the maze is "valid" or "invalid". **Input Specification:** 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 Specification:** For each test case find whether the maze is "valid" or "invalid". **Input Constraints:** 1

N/A

N/A