{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"MD","content":"Actualmente, existen muchos algoritmos para generar laberintos, recomendamos leer más acerca de ellos:\n[https://en.wikipedia.org/wiki/Maze_generation_algorithm](https://en.wikipedia.org/wiki/Maze_generation_algorithm)\n\nDespués de probar algunos de estos algoritmos notamos que no siempre funcionan bien, al generar un nuevo laberinto, tenemos que checar si es válido o no. Un laberinto válido tiene exactamente un punto de entrada y exactamente un punto de salida (exactamente 2 aperturas en sus lados) y existe al menos un camino desde el punto de entrada al punto de salida.\n\n![Laberinto](https://i.pinimg.com/736x/d8/7a/0e/d87a0e5951a944c51ae2bb0e35f9d463.jpg)\n\nTe damos un laberinto, solo busca si es un laberinto válido o no.\n\n### Input\nThe 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 `m x n`. `M[i][j]\u003d\u0027#\u0027` represents a wall and `M[i][j]\u003d\u0027.\u0027` represents a space.\n\n- `1\u003c\u003dt\u003c\u003d10000`\n- `1\u003c\u003dm,n\u003c\u003d20`\n\n### Output\nFor each test case find whether the maze is \"valid\" or \"invalid\".\n\n### Examples\n\n#### Input\n```\n6\n4 4\n####\n#...\n#.##\n#.##\n5 5\n#.###\n#..##\n##..#\n#.#.#\n###.#\n1 1\n.\n5 1\n#\n#\n.\n.\n#\n2 2\n#.\n.#\n3 4\n#..#\n#.##\n#.##\n```\n#### Output\n```\nvalid\nvalid\ninvalid\nvalid\ninvalid\ninvalid\n```"}}]}