시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB159262035.088%

문제

어떤 n×m(1 ≤ n, m ≤ 100)의 이진 행렬이 있다. 이진 행렬이라는 것은 0과 1로만 된 행렬이라는 뜻이다.

이 행렬에서 Reverse(x, y)라는 연산이 정의되어 있다. 행렬의 (x, y)에 원래 저장되어 있던 값을 k라고 하자. 이 함수를 수행하면 (x, y)와 인접(상하좌우)해 있는 칸들 중에서 그 행렬 값이 k인 위치로 퍼져 나가면서, 행렬 값을 1-k(즉, 0을 1로, 1을 0으로)로 바꾼다. x는 행 번호, y는 열 번호이다. 행렬의 행 번호와 열 번호는 1부터 시작한다.

예를 들어 11000111과 같은 1×8의 행렬이 있다고 해 보자. Reverse(1,1)을 수행하면 00000111이 되고, Reverse(1,4)를 수행하면 11111111이 된다.

이와 같은 Reverse 함수를 최소로 이용하여, 전체 행렬에 저장되어 있는 값을 같은 값(0 또는 1)로 바꾸는 것이 목적이다.

입력

첫째 줄에 n, m이 주어진다. 다음 n개의 줄에는 m개의 수로 행렬이 주어진다.

출력

첫째 줄에 함수의 호출 회수 K를 출력한다. 다음 K개의 줄에는 x, y를 출력한다. 이는 차례로 Reverse(x, y)의 함수를 호출하였다는 의미이다.

예제 입력 1

9 9
001111100
010000010
100101001
100101001
100000001
101000101
100111001
010000010
001111100

예제 출력 1

2
2 3
3 1