30702번 - 국기 색칠하기

문제

세계의 여러 나라들은 자신의 나라를 상징하는 깃발인 국기가 있는데, 그중에는 색만 다르고 모양이 비슷한 국기들이 있다. 국기는 $N$행 $M$열의 격자판(행렬)으로 구성되어 있다. 격자판의 각 칸을 이루는 색은 A부터 Z까지의 영어 알파벳 대문자로 표현한다.

$A[i][j]$를 국기 $A$의 $i$행 $j$열의 색이라고 하자. 두 국기 $A,B$ 가 주어졌을 때, 모든 $i,j(1\leq i\leq N;$ 1ドル\leq j\leq M)$에 대해 $A[i][j]$와 $B[i][j]$가 같으면 둘은 같은 국기이다.

근호는 국기 $A$와 $B$를 가지고 있고, 국기 $A$를 적절히 색칠하여 국기 $B$와 같게 만들려고 한다. 국기를 색칠할 때는 다음과 같은 동작을 0ドル$회 이상 반복한다.

• 국기의 격자판 중 한 칸을 고르고, 이 칸과 같은 구역에 속한 모든 칸을 찾는다. 두 칸이 같은 색이면서 상하좌우로 인접해 있을 경우 둘은 같은 구역에 속한다. 이후, 해당하는 구역의 칸들의 색을 원하는 다른 색으로 바꾼다. 이 때, 영어 알파벳 대문자 외에도 임의의 다른 색을 새로 사용할 수 있다.

근호가 가진 국기 두 장의 정보가 주어졌을 때, 국기 $A$를 적절히 색칠해 국기 $B$와 똑같이 만들 수 있는지 판별하여라. 국기를 돌리거나 뒤집을 수는 없음에 유의하라.

입력

첫 번째 줄에 국기의 행 개수 $N$과 열 개수 $M$이 공백으로 구분되어 정수로 주어진다.(3ドル\leq N, M\leq 50$)

이후 $N$개의 줄에는 국기 $A$의 각 칸을 이루는 색이 줄마다 길이 $M$의 문자열로 주어진다. 이 중 $i$번째 줄의 $j$번째 문자가 $A[i][j]$를 나타낸다. 각 문자열은 영어 알파벳 대문자로만 이루어져 있다.

그다음 $N$개의 줄에는 국기 $B$의 각 칸을 이루는 색이 위와 동일한 형식으로 주어진다.

출력

국기 $A$를 적절히 색칠하여 국기 $B$와 같게 만들 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.

제한

힌트