## 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".

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```

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <iostream>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;

typedef pair<int,int> ii;
typedef vector<vector<pair<int,ii>>  > vviii;
#define se second
#define fi first
#define pb push_back

const int INF = 0x3f3f3f3f;

vector<string> grid;
vector<string> visited;

int dx[] = {-1,1,0,0};
int dy[] = {0,0,1,-1};

int m,n,count,ecount;

void dfsUtil(int starti,int startj){
stack<ii> st;
st.push(ii(starti,startj));
visited[starti][startj]='T';
while(!st.empty()){
ii top = st.top();
st.pop();
for(int i=0;i<4;++i){
int cx = top.fi+dx[i];
int cy = top.se+dy[i];
if(cx<0||cx>m-1||cy<0||cy>n-1||grid[cx][cy]=='#'||visited[cx][cy]=='T')
continue;
if(cx==0||cy==0||cx==m-1||cy==n-1){
count++;
}
st.push(ii(cx,cy));
visited[cx][cy]='T';
}
}
}

void dfs(){
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(grid[i][j]=='.'&&(i==0||j==0||i==(m-1)||j==(n-1))){
ecount++;
dfsUtil(i,j);
if(count>1){
return ;
}
// reset visited if no path found
else if(count==0){
visited = vector<string> (m,string(n,'F'));
}
}
}
}
}

int main(){
int t;
scanf("%d",&t);
while(t--){
count=0;
//count the number of openings on the edges
ecount=0;
scanf("%d %d",&m,&n);
grid = vector<string> (m,string());
visited = vector<string> (m,string(n,'F'));
string input;
for(int i=0;i<m;++i){
cin>>input;
grid[i]=input;
}
dfs();
if(count>1||count==0||ecount>2){
printf("invalid\n");
}
else{
printf("valid\n");
}
}
return 0;
}``````
Copy The Code &

Input

cmd
6
4 4
####
#...
#.##
#.##
5 5
#.###
#..##
##..#
#.#.#
###.#
1 1
.
5 1
#
#
.
.
#
2 2
#.
.#
3 4
#..#
#.##
#.##

Output

cmd
valid
valid
invalid
valid
invalid
invalid