지식재산권 | cho.sh

문제

에라스트 코피는 유명한 스도쿠 퍼즐 제작자다. 그가 낸 퍼즐 모음집이 크게 성공하자 모방작과 표절작이 여럿 나왔다. 코피는 소송을 걸기 전에 증거를 더 모으기로 했다.

스도쿠 퍼즐은 $9 \times 9$ 표이고, 칸 $3 \times 3$ 개로 이루어진 작은 표 $3 \times 3$ 개로 나뉜다. 각 칸에는 1부터 9까지의 숫자를 하나 넣을 수 있다. 퍼즐의 목표는 각 행, 각 열, 그리고 $3 \times 3$ 작은 표 아홉 개마다 1부터 9까지의 숫자가 정확히 한 번씩 들어가도록 빈 칸을 채우는 것이다.

코피는 스도쿠 퍼즐 데이터베이스를 가지고 있고, 그 안에 비슷한 퍼즐이 있는지 알고 싶다. 다음 연산을 여러 번 적용해 퍼즐 $P$ 를 퍼즐 $Q$ 로 바꿀 수 있으면 퍼즐 $P$ 는 퍼즐 $Q$ 와 비슷하다.

숫자 $x$ 와 $y$ 를 골라 모든 $x$ 를 $y$ 로, 모든 $y$ 를 $x$ 로 바꾼다.
행 묶음 $(1, 2, 3)$ , $(4, 5, 6)$ , $(7, 8, 9)$ 중 두 묶음을 통째로 맞바꾼다.
같은 묶음에 속한 두 행을 맞바꾼다.
열 묶음 $(1, 2, 3)$ , $(4, 5, 6)$ , $(7, 8, 9)$ 중 두 묶음을 통째로 맞바꾼다.
같은 묶음에 속한 두 열을 맞바꾼다.
왼쪽 위 모서리와 오른쪽 아래 모서리를 잇는 대각선을 축으로 뒤집는다. 이 연산을 하면 열이 행이 되고 행이 열이 된다.

데이터베이스에서 비슷한 퍼즐을 찾아 코피를 도와주자.

입력

첫 줄에 데이터베이스에 든 퍼즐의 개수 $n$ 이 주어진다. ( $1 \le n \le 20$ )

이어서 퍼즐 $P_1, P_2, \dots, P_n$ 의 정보가 주어진다. 퍼즐 하나는 아홉 줄로 이루어지고 각 줄은 문자 아홉 개다. 각 문자는 1부터 9까지의 숫자이거나, 빈 칸을 뜻하는 점 .이다. 연속한 두 퍼즐 사이에는 빈 줄이 하나 들어간다.

입력에 공백은 없다. 퍼즐을 풀 수 있다는 보장은 없으므로 한 행이나 한 열에 같은 숫자가 여러 번 나올 수도 있다.

출력

$1 \le i < j \le n$ 인 모든 쌍 $(i, j)$ 에 대해, 퍼즐 $P_i$ 가 퍼즐 $P_j$ 와 비슷하면 Yes를, 비슷하지 않으면 No를 한 줄에 하나씩 출력한다.

쌍의 순서는 $(1, 2), (1, 3), \dots, (1, n), (2, 3), (2, 4), \dots, (n - 1, n)$ 이다. 즉 먼저 $P_1$ 을 $P_2, P_3, \dots, P_n$ 과 차례로 비교하고, 다음으로 $P_2$ 를 $P_3, P_4, \dots, P_n$ 과 차례로 비교하는 식으로 진행한다.