Matrix Path with Alternating Digits

Given an n x m matrix with entries consisting of 0's and 1's, each cell denoted as (i, j) for 1 \leq i \leq n and 1 \leq j \leq m, you are to find a shortest path from the top‐left cell (1, 1) to the bottom‐right cell (n, m) under the following conditions:

• You can move from cell (i, j) to any of its four adjacent cells: (i-1, j), (i+1, j), (i, j-1), or (i, j+1).
• You must remain within the bounds of the matrix at all times, that is, your current position should always satisfy 1 \leq i \leq n and 1 \leq j \leq m.
• When moving from one cell to an adjacent cell, the number in the source and destination cells must be different. In other words, a cell with a 0 can only move to a cell with a 1 and vice versa.

Each move takes one unit of time. Your task is to output the minimum time required to travel from (1, 1) to (n, m) and also provide one corresponding shortest path. The path should be represented as a sequence of coordinates starting with (1, 1) and ending with (n, m). If no valid path exists, output -1.

Note: The time cost is defined as the number of moves made. For example, if you move from (1,1) to (1,2) to (2,2), the cost is 2 units, and the path length (number of cells listed) is 3.

inputFormat

The first line contains two integers n and m (1 \leq n, m). The following n lines each contain m integers (each being 0 or 1), representing the matrix.

outputFormat

If a valid path exists, output the minimum time (number of moves) on the first line, followed by t+1 lines where each line contains two integers representing the 1-indexed row and column of each step in the path. If no path exists, output -1.

sample

2 2
0 1
1 0

2
1 1
1 2
2 2