We consider cases based on the parity of \(N\) and \(M\).

1. When both \(N\) and \(M\) are odd

If the center square is 0, Second wins. Second can always make the center square 0 by eating pieces on the opposite side from where First ate.

Also, when the center three vertical squares or horizontal squares are 010, Second wins. When First eats a row or column for the first time, by eating the same side as First ate, the center square becomes 0 and Second wins.

Otherwise, we perform one step of simulation to reduce to the case when exactly one of \(N\) and \(M\) is odd, described below.

2. When exactly one of \(N\) and \(M\) is odd

Without loss of generality, assume \(N\) is odd. When either of the center two squares is 1, First wins (similar to when the center square is 0 when both \(N\) and \(M\) are odd).

Also, when any of the center two columns has three vertical squares forming 101, First wins (similar to when three vertical squares are 010 when both \(N\) and \(M\) are odd).

Otherwise, Second wins. In this case, the center two squares are 00, and neither of the center two columns has three vertical squares forming 101. Second’s strategy is basically to eat the opposite side from where First ate. Here, depending on First’s move, one of the following occurs:

• When First can only choose to eat a column, Second can pass the turn to First with a board where the center two squares are 00, and Second wins.
• When First can only choose to eat a row, since neither of the center two columns had three vertical squares forming 101, Second can again pass the turn to First with a board where the center two squares are 00, and Second wins.

3. When both \(N\) and \(M\) are even

By performing one step of simulation, we can reduce to the case where only one of \(N\) or \(M\) is odd.

Summarizing the above, we see that this game is determined only by the center area. The game outcome can be determined in \(O(1)\), and receiving the input takes \(O(NM)\), which is the bottleneck.