17083번 - 그리드랜드 스페셜 저지

백양로의 구석진 곳에는 비밀의 도시 ‘그리드랜드’ 로 향하는 문이 하나 있다. 이 도시에 발을 들이는 연세대학교 학생은 미션을 하나 받게 되며, 해결할 경우 졸업할 때까지 모든 과목에서 A+를 받게 된다는 전설이 있다.

이 비밀의 도시는 N×M 직사각형 격자 그리드 형태로 이루어져 있으며, N×M개의 각 칸은 비어 있거나, 집이 한 채 있거나, 울창한 나무가 서 있다. 어떤 두 집이 가로 또는 세로로 일직선상에 있으며, 두 집 사이에 나무 또는 다른 집이 없을 때, 이 두 집은 서로를 볼 수 있다. 그리드랜드의 미션은 단순하다. 각 집의 지붕에 'Y', 'O', 'N', 'S', 'E', 'I' 중 하나의 문자를 그려넣어, 서로를 볼 수 있는 모든 두 집이 서로 다른 문자를 받게 하면 된다.

그러나 이 도시에는 수백 년 동안 사람의 발길이 없었고, 그 사이에 문자 'I'를 그릴 수 있는 도장은 고장나 버렸으며, 설상가상으로 주민들은 두 파벌로 나누어 싸우기 시작했다. 두 파벌 간의 사이는 매우 나빠서, 만약 서로 다른 파벌 출신의 두 주민의 집 지붕에 같은 문자가 그려진다면 이들은 매우 화를 내며 미션 완수를 인정하지 않을 것이다.

우연히 이 도시에 들어오게 된 택희는 지금껏 들어왔던 것과는 많이 다른 상황에 당황했지만, 곧 'Y', 'O', 'N', 'S', 'E' 다섯 개의 문자를 지붕에 적절히 그려넣으며 아래의 두 조건,

• 서로 볼 수 있는 두 집의 지붕엔 다른 문자가 그려져야 한다
• 서로 다른 파벌의 사람이 사는 두 집 지붕에는 다른 문자가 그려져야 한다.

을 모두 만족하는 배정을 찾아내어 미션을 완수하기로 마음먹었다.

택희를 도와 도시 내의 모든 집 지붕에 적절한 문자를 배정하는 것이 가능한지 판정하고, 가능하다면 임의의 배정 하나를 찾아내는 프로그램을 작성해보도록 하자.

첫째 줄에 그리드랜드의 행의 수 N과 열의 수 M이 주어진다. (1 ≤ N, M ≤ 1000)

이어 N개의 줄에 M개의 문자로 그리드랜드의 모습이 주어진다. 각 문자는 ‘.’, ‘#’, ‘1’, ‘2’ 중 하나로, ‘.’은 빈 칸을, ‘#’은 나무가 자란 칸을, ‘1’은 파벌 1 주민의 집을, ‘2’는 파벌 2 주민의 집을 의미한다.

첫째 줄에, 적절한 배정이 가능하다면 YES를, 불가능하다면 NO를 출력한다.

만약 첫째 줄에 YES를 출력했다면 이어 N개의 줄에 M개의 문자로, 각 집의 지붕에 적은 문자를 ‘Y’, ‘O’, ‘N’, ‘S’, ‘E’ 중 하나로 바꾸어 출력한다. 빈 칸과 나무가 있는 칸은 입력과 동일해야 하며, 모든 집은 조건을 만족하도록 문자 하나씩을 받아야 한다.

여러 가지 정답이 존재한다면 그중 아무 것이나 하나만 출력한다.