Trail of No Return
A token is placed on the cell marked S in an board. Some cells are blocked.
Two players share the token and take turns, with the first player moving first. On each turn, the player must move the token to an orthogonally adjacent cell that is neither blocked nor previously visited. Cells that share a side are orthogonally adjacent.
The starting cell is considered visited before the first turn. Whenever the token enters another cell, that cell becomes visited and remains visited for the rest of the game.
A player who has no legal move on their turn loses. Both players play optimally. Determine which player wins.
Input
The first line contains two integers and , the dimensions of the board.
The next lines each contain a string of length describing one row of the board. Each character is one of the following:
S, the starting cell;., an open cell;#, a blocked cell.
The board contains exactly one S.
Output
Print First if the first player wins with optimal play. Otherwise, print Second.
Samples
Sample 1
Input
1 1 S
Output
Second
The token has no legal destination, so the first player loses immediately.
Sample 2
Input
1 2 S.
Output
First
The first player moves to the only other cell, after which the second player has no legal move.
Sample 3
Input
2 3 S#. ...
Output
Second
The open cells form a single route on which exactly four moves are possible. The second player makes the last move.