SP11516 MAKEMAZE - VALIDATE THE MAZE

**迷宫生成** 在计算机科学中，有很多种算法可以用来生成迷宫（相关信息可参考：[迷宫生成算法 - 维基百科](http://en.wikipedia.org/wiki/Maze_generation_algorithm)）。一旦生成出迷宫，我们就需要验证它是否符合有效迷宫的标准。一个有效的迷宫必须满足以下条件： - 只有一个入口和一个出口（即边界上有且只有两个开口） - 从入口到出口之间必须存在至少一条路径 给定一个迷宫，你需要判断它是“有效”还是“无效”。

输入的第一行为整数 $t$，表示测试用例的个数。接下来的每个测试用例，第一行包含两个整数 $m$ 和 $n$，分别表示迷宫的行数和列数。接下来是一个 $m \times n$ 的矩阵 $M$，用来描述迷宫结构。矩阵中，$M[i][j] = \#$ 表示位置是墙，$M[i][j] = \text{.}$ 表示位置是空地。

对于每个测试用例，判断迷宫是否有效，并输出“valid”或“invalid”。

- $1 \le t \le 10000$ - $1 \le m \le 20$ - $1 \le n \le 20$ ### 示例输入： ``` 6 4 4 #### #... #.## #.## 5 5 #.### #..## ##..# #.#.# ###.# 1 1 . 5 1 # # . . # 2 2 #. .# 3 4 #..# #.## #.## ``` ### 示例输出： ``` valid valid invalid valid invalid invalid ``` **本翻译由 AI 自动生成**