Minimum New Roads

You are given a grid of size m×n where each cell contains either a 0 or a 1. A cell with a 0 represents a road, while a cell with a 1 represents a building. Initially, the main bus station is located at the top‐left corner (cell (0,0)). Your task is to determine the minimum number of new roads that need to be constructed (i.e. converting building cells to road cells) so that every cell that originally contained a road is connected (reachable) from the bus station using only moves in the four cardinal directions (up, down, left, right).

Note: If the bus station cell (0,0) is not a road, or if it is impossible to connect all the road cells regardless of the conversions, output -1.

The cost of converting a cell is considered 1 per cell. In other words, if you decide to transform some building cells to roads such that the graph induced on the set of cells (original roads and converted cells) becomes connected among all original road cells, the total cost is the number of cells you have converted. Formally, if we denote by \(C\) the set of cells that were originally buildings and are converted, then your answer is:

[ \text{Answer} = |C| ]

Your solution must read input from stdin and write the answer to stdout.

inputFormat

The first line of the input contains two integers m and n, which represent the number of rows and columns of the grid, respectively.

This is followed by m lines, each containing n integers (each either 0 or 1) separated by spaces representing the grid.

For example:

3 4
0 1 0 0
1 1 1 0
0 0 0 1

outputFormat

Output a single integer — the minimum number of new roads to be constructed to connect all the road (0) cells to the bus station at (0,0). If it is impossible, output -1.

## sample

3 4
0 1 0 0
1 1 1 0
0 0 0 1

2