Minimum Piece Removal for Disconnecting Chessboard

The problem is as follows:

You are given a chessboard consisting of an \(n \times m\) grid. Each cell can contain at most one chess piece. Initially, several pieces are placed on the board. Two pieces are considered to be in the same connected component if they are adjacent horizontally or vertically.

Your task is to remove as few pieces as possible so that the remaining pieces form at least two connected components. Note that you are only allowed to remove pieces; you cannot move them. If it is impossible to achieve this, output \( -1 \).

Important: The remaining pieces must number at least two in order to form two or more connected groups.

Hint: If the board is already disconnected (i.e. there are at least two connected components), then the answer is \(0\). Otherwise, check if removal of a single piece makes the board disconnected; if not, then the answer is \(2\) (provided that the number of pieces is at least \(3\)).

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of rows and columns of the grid).

Then follow \(n\) lines each containing \(m\) space‐separated integers. Each integer is either \(0\) or \(1\), where \(1\) denotes a cell containing a chess piece and \(0\) denotes an empty cell.

outputFormat

Output a single integer indicating the minimum number of chess pieces that need to be removed so that the remaining pieces form at least two connected components. If it is impossible, output \( -1 \).

sample

2 2
1 1
1 0

1