Cat Snuke and wolf Sothe are playing the Connecting Game.
The Connecting Game is played on a rectangular grid that is divided into unit square cells.
The grid is divided into some regions.
Each cell belongs into exactly one of those regions.
Each region is 4-connected (see Notes for a formal definition).
You are given a String[] board that describes the division of the grid into regions.
Each character in board represents one of the cells.
Cells that are represented by the same character belong into the same region.
Initially, the entire grid is colorless.
During the game, the players color some of the regions red and other regions blue.
(Within each region, all cells must have the same color.)
The game ends when the entire board is colored.
The actual rules of the game are not important.
The only information you need is that at the end of the game each combination of red and blue regions is possible.
At the end, the game is evaluated as follows:
- If there is a path (see Notes for a formal definition) of blue cells from the top row to the bottom row, Snuke wins.
- If there is a path of red cells from the left column to the right column, Sothe wins.
Obviously, it is impossible for both players to win the game at the same time.
However, sometimes there can be no winner.
Your task is to recognize game boards for which this may happen.
Formally, a board is called valid if it is guaranteed that the game will have a winner, and invalid if it is possible that there is no winner at the end of the game.
You are given the String[] board.
Return "valid" (quotes for clarity) if it represents a valid board, or "invalid" if it does not. | 
