26085번 - 효구와 호규 (Easy)

효구는 $N$개의 행과 $M$개의 열로 이루어진 $N \times M$ 크기의 격자판을 갖고 있다. 각 칸에는 하나의 카드가 놓여 있으며, 카드에는 $0$ 또는 $1$의 숫자가 적혀 있다.

깔끔한 걸 좋아하는 형 호규는 격자판의 모든 카드를 없애려고 한다. 단, 호규는 아래의 두 가지 행동만을 원하는 만큼 수행할 수 있다.

• 동일한 숫자를 가진 두 카드가 인접해 있으면 두 카드를 없앤다.
• 카드 하나를 골라 카드가 없는 인접한 칸으로 옮긴다.

여기서 인접해 있다는 것은 상하좌우 네 방향 중 한 방향으로 인접해 있음을 의미한다.

호규가 모든 카드를 없앨 수 있는지 알아보자.

첫 번째 줄에는 격자판의 크기를 나타내는 두 정수 $N$과 $M$이 주어진다. ($3 \le N, M \le 1\,000$)

두 번째 줄부터 $N+1$ 번째 줄까지는 격자판의 정보가 주어진다. 각 줄에는 $M$개의 숫자가 공백으로 구분되어 주어지며, $i+1$번째 줄의 $j$번째 숫자는 $i$행 $j$열에 놓인 카드의 숫자를 의미한다. 단, 각 숫자는 $0$ 또는 $1$이다.

모든 카드를 없앨 수 있으면 $1$을 출력하고, 그렇지 않으면 $-1$을 출력한다.