Problem E
2D Nim

Game Theory is an important tool in a mathematician’s toolbox. It provides a framework to analyze how individuals make choices in situations influenced by the decisions of others, offering insights into cooperation, competition, and conflict resolution. With applications spanning from economic business strategy to evolutionary biology, game theory remains a fundamental tool for deciphering the dynamics of human interaction. In this problem, we will explore how two skilled players will act in a toy game theory problem.

The two players alternate making moves on an $n$ by $m$ grid. Initially each grid cell either contains a square tile or is empty. Player 1 always goes first. On each player’s turn, they must choose a non-empty row or column of the grid and remove one or more tiles from that row or column. The removed tiles do not need to be contiguous but they must all come from the single row or column. If a player cannot make a move (because there are no tiles left to take), that player loses.

The game tree of potential moves that players can make on a $2 \times 2$ grid (up to symmetries of the grid) are shown below. Player 1 has an optimal winning strategy if the game begins with the grid initially in one of the black states. Likewise, player 2 has an optimal winning strategy for red initial grid states (including an empty grid).

Given the initial state of the grid, determine which player wins, assuming both players play optimally.

Input

The first line contains a positive integer $n$, the number of rows in the grid. The second line contains another positive integer $m$, the number of columns in the grid. The next $n$ lines each contain $m$ characters each, representing one row of the initial grid state. Each character is either 0, representing an empty grid cell, or 1, representing a cell initially containing a tile.

Output

Print the number of the player (either $1$ or $2$) who wins the game if both players play optimally.

Scoring

Your solution will be evaluated on three test sets. In the first test set, worth $25\% $ of the points, the grid size respects the bounds $1 \leq n, m \leq 4$. In the second test set, worth $25\% $ of the points, the grid has size $1 \leq n,m \leq 5.$ Finally in the third test set the grid has size $1 \leq n, m \leq 100$ but at most $20$ of the cells initially contain a tile.

1
10
1111111111

1

3
3
111
011
001

2