35281번 - 가지가지 스페셜 저지

$N \times M$ 크기의 격자판에 $1 \times 2$ 크기의 도미노 형태인 가지를 놓으려고 한다. 가지는 다음 규칙에 따라 배치되어야 한다.

• 각 가지는 꼭지와 몸통이 각각 $1$칸을 차지하는 모양이다.
• 가지의 꼭지는 항상 몸통의 왼쪽 또는 위쪽에 있어야 한다.
• 격자판의 모든 행과 열에 꼭지가 홀수 개 존재해야 한다. $0$은 홀수가 아니다.
• 가지끼리는 겹칠 수 없다.

이러한 규칙을 만족하면서 가지를 배치할 때, 필요한 가지의 최소 개수와 배치 방법을 출력하시오.

첫 번째 줄에 격자판의 행의 개수와 열의 개수를 나타내는 두 정수 $N$, $M$이 공백으로 구분되어 주어진다. ($2 \le N, M \le 1\,000$)

첫 번째 줄에 필요한 가지의 최소 개수를 출력한다. 만약 조건을 만족하는 배치 방법이 없다면 -1을 출력한다.

배치가 가능하다면, 두 번째 줄부터 $N$개의 줄에 걸쳐 격자판의 상태를 출력한다. 각 줄은 공백 없이 붙여진 길이 $M$의 문자열이어야 한다.

각 문자의 의미는 다음과 같다.

• .: 빈 칸
• G: 가지의 꼭지
• g: 가지의 몸통

가능한 배치 방법이 여러 가지라면 그중 아무거나 출력한다.