Game of Connectivity

Two players, I and J, play a game on an $n \times m$ grid. The grid has cells denoted by $(x,y)$ for the $x$-th row and $y$-th column, where $1 \le x \le n$ and $1 \le y \le m$. Each cell is initially either white or black with the guarantee that at least one cell is white. In a valid game state the two special cells $(1,1)$ and $(n,m)$ are white and connected via a path of adjacent (sharing a side) white cells.

Players take turns, with player I moving first. In each move, the current player must choose exactly one white cell and paint it black. However, if after a move at least one of the following conditions holds:

• Cell $(1,1)$ is no longer white,
• Cell $(n,m)$ is no longer white, or
• There is no path (via adjacent white cells) between $(1,1)$ and $(n,m)$, i.e. these two cells are not in the same four-connected white component,

then the player who performed that move immediately loses and the other player wins.

Under perfect play from both sides, determine who will win the game. The key observation is that a move is only legal if it does not disconnect the connectivity between $(1,1)$ and $(n,m)$. In other words, players are only allowed to remove a white cell if it is non-critical for maintaining the connectivity between the endpoints. We can define the set of mandatory cells as those that lie on every white path between $(1,1)$ and $(n,m)$ (note that the endpoints themselves are always mandatory). Since a move that removes a mandatory cell would break connectivity (or remove an endpoint) and thus lose immediately, the only moves available are on the safe cells – those white cells that are not mandatory.

If there are s safe moves available in total (i.e. the total number of white cells minus the number of mandatory cells), then the game becomes a take-away game where each move removes one safe cell. Under optimal play, if s is nonzero and odd, player I (the first mover) wins; otherwise, player J wins. Note that if no safe move exists at the start (i.e. s = 0), then player I loses immediately because he has no legal move.

Task: Given the grid configuration, determine the winner: output I if player I wins and J otherwise.

inputFormat

The first line contains two integers $n$ and $m$ ($n, m \ge 1$), denoting the number of rows and columns of the grid. Each of the next $n$ lines contains a string of length $m$. Each character is either W (representing a white cell) or B (representing a black cell). It is guaranteed that at least one cell is white and that in a valid game state, both $(1,1)$ (top‐left) and $(n,m)$ (bottom‐right) are white and connected through white cells.

outputFormat

Output a single character: I if player I wins under optimal play, or J otherwise.

sample

2 2
WW
WW

J