Minimum Lights to Illuminate the Grid

You are given a grid with m rows and n columns. Each cell in the grid is represented by a character: '1' indicates that the cell already has a light and '0' indicates darkness. A row (or column) is considered illuminated if at least one cell in that row (or column) contains a light. Your task is to determine the minimum number of additional lights needed so that every row and every column becomes illuminated, and to output one valid configuration (i.e. the coordinates of the lights to be added).

Illumination Criteria:

• A row is illuminated if it contains at least one '1' or if a light is added in that row.
• A column is illuminated if it contains at least one '1' or if a light is added in that column.

Hint: Let \(R\) be the set of rows without any pre-existing light, and \(C\) be the set of columns without any pre-existing light. By placing a light at an intersection of a dark row and a dark column, you can cover both simultaneously.

The grid indices are 0-indexed. If a dark row does not have any dark column available (i.e. all columns are already illuminated by other rows), you may place a light in any column (for instance, column 0) to illuminate that row.

inputFormat

The first line contains two integers m and n separated by a space, representing the number of rows and columns, respectively. The next m lines each contain a binary string of length n, where each character is either '0' or '1'.

Example:

3 3
111
111
111

outputFormat

The first line of output should contain a single integer representing the minimum number of additional lights required. If additional lights are needed, each of the following lines should contain two integers i and j (0-indexed) separated by a space, representing the row and column indices where a light is to be added.

Example (corresponding to the above input):

0

## sample

3 3
111
111
111

0

</p>