연결된 지배 집합

무향 그래프 $G=(V,E)$에서 다음 조건을 만족하는 정점 집합 $S$를 그래프 $G$의 지배 집합이라고 합니다.

• $S$에 속하지 않는 모든 정점 $v$에 대해, 간선 $(u,v)$가 $E$에 속하도록 하는 정점 $u \in S$가 하나 이상 있습니다.

다음 조건을 만족하는 정점 집합 $S'$를 그래프 $G$의 연결된 지배 집합이라고 합니다.

• $S'$는 그래프 $G$의 지배 집합입니다.
• 그래프 $G$에서 $S'$에 의해 유도된 부분 그래프가 연결 그래프입니다.

요약하면, $G$의 모든 정점은 $S'$에 속하거나 $S'$의 정점과 인접해야 하며, $S'$에 속한 임의의 두 정점 $u$, $v$는 $S'$의 정점만 거치는 경로로 이어져 있어야 합니다.

$n$개의 행과 $m$개의 열이 있고, 상하좌우로 인접한 모든 두 칸 사이에 간선이 있는 격자 그래프를 생각합니다. 이 그래프의 정점은 $nm$개이고, 간선은 $2nm-n-m$개입니다. 흐즈로는 이 그래프에 대해 다음 가설을 세웠습니다.

• $2$ 이상의 임의의 $n$과 $m$에 따라 정의된 격자 그래프에는 크기가 $\frac{nm}{2}$ 이하인 연결된 지배 집합 $D$가 존재합니다.

흐즈로는 매우 많은 경우에 이 사실이 성립함을 직접 증명했습니다. 그러나 모든 경우에 대해 증명된 것은 아니므로, 일부 경우에는 이 가설이 틀렸을 수도 있습니다. $n$과 $m$이 주어졌을 때, 크기가 $\frac{nm}{2}$ 이하인 연결된 지배 집합 $D$가 존재하는지 판단하고, 존재한다면 그 집합 $D$를 출력하세요.

한 줄에 행의 개수 $n$과 열의 개수 $m$이 공백으로 구분되어 주어집니다. ($2 \le n,m \le 1000$)

조건을 만족하는 집합 $D$가 존재하면 YES를 출력합니다. 그다음 줄부터 $n$개의 행에 걸쳐 아래 설명에 따라 집합 $D$를 출력합니다.

$D$를 나타내기 위해 길이가 $m$인 문자열을 $n$개의 줄에 출력합니다. 각 문자는 다음과 같아야 합니다.

• $i$번째 행과 $j$번째 열의 정점이 $D$에 포함되어 있으면, $i$번째 줄의 $j$번째 문자는 1입니다.
• 그렇지 않으면, $i$번째 줄의 $j$번째 문자는 0입니다.

조건을 만족하는 집합 $D$가 여러 개라면 그중 어느 것을 출력해도 정답으로 인정합니다.

조건을 만족하는 집합 $D$가 존재하지 않으면 한 줄에 NO를 출력합니다.

그래프 $G=(V,E)$와 정점 집합 $A \subseteq V$에 대해, $A$에 의해 유도된 부분 그래프는 $A$에 속한 정점과, 양 끝점이 모두 $A$에 속하는 간선 전부로 이루어진 부분 그래프입니다.

연결된 지배 집합의 정의가 이해되지 않는다면 영어 위키백과의 Connected dominating set 문서를 참고하세요.