31467번 - 초콜릿 괴도 코코 (Bitter)

문제

추리 소설 “초콜릿 괴도 레나”를 감명 깊게 읽은 코코는 이 소설의 명장면을 따라 해 보기로 했다. 구체적인 방법은 다음과 같다.

• 1단계: 먼저 $N\times N$ 크기의 사각 격자 형태의 초콜릿을 준비한다. 이 초콜릿은 1ドル\times 1$ 단위로 원하는 곳에서 떼어낼 수 있게 되어 있으며, 0ドル$개 이상의 단위 초콜릿이 제거된 상태이다. 이때, 남아있는 단위 초콜릿은 4ドル$개 이상이며, 한 조각을 이루어야 한다. 상하좌우로 이웃한 두 단위 초콜릿은 서로 연결되어 있으며, 서로 연결된 단위 초콜릿들의 집합을 하나의 조각이라고 한다.
• 2단계: 이 초콜릿에서 다음의 조건을 충족하도록 하나의 단위 초콜릿을 떼어 먹는다.
  • 이 단위 초콜릿을 떼어낸 후에도 남아있는 초콜릿은 하나의 조각을 이루지만, 그 이후에 서로 이웃한 임의의 두 단위 초콜릿 사이를 자르면 2ドル$개의 조각으로 나누어진다.
• 3단계: 레나의 명대사를 외친다. “이번엔 봐줬지만, 다음에는 반드시 초콜릿을 조각내 줄 거야.”

코코는 1단계의 조건을 충족하는 초콜릿을 준비해 놓았지만, 2단계의 조건을 충족하려면 어느 지점에 있는 단위 초콜릿을 떼어내야 할지 고민에 빠졌다. 코코를 도와주자.

입력

첫 번째 줄에는 초콜릿의 크기 $N$이 주어진다. $(2\le N\le 1,円 000)$

두 번째 줄부터 $N$줄에 걸쳐서 초콜릿의 상태가 주어진다. 각 줄에는 각 칸에 단위 초콜릿이 있는지를 나타내는 문자 $N$개가 공백 없이 주어진다. 각 문자는 모두 # 또는 .이며, 초콜릿의 $r$번째 줄의 $c$번째 글자가 #이면 $r$행 $c$열에 단위 초콜릿이 있음을, .이면 없음을 뜻한다. 초콜릿의 맨 왼쪽 위 칸은 1ドル$행 1ドル$열이다.

모든 입력은 1단계의 조건을 충족한다.

출력

첫 번째 줄에는 2단계의 조건을 충족하도록 떼어낼 수 있는 서로 다른 단위 초콜릿의 개수를 출력한다.

다음 줄부터는 그러한 단위 초콜릿의 행 번호와 열 번호를 한 줄에 하나씩 출력한다. 이때, 행 번호가 작은 것부터, 행 번호가 같은 것들 중에서는 열 번호가 작은 것부터 출력한다.

제한

힌트