Nastya 来上她的信息学课,顺便说一下,她的老师在这里有点名气,给了她以下任务。
给出两个矩阵 $$$A$$$ 和 $$$B$$$,每个矩阵的大小为 $$$n \times m$$$。 Nastya 可以对矩阵 $$$A$$$ 执行以下操作无限次:
- 取 $$$A$$$ 的任意方方子矩阵并将其转置(即子矩阵中位于 $$$i$$$ 行和 $$$j$$$ 列的子矩阵转置后将位于 $$$j$$$ 行和 $$$i$$$ 列,转置后的子矩阵本身将保留其在矩阵中的位置$$$A$$$)。
Nastya 的任务是检查是否可以将矩阵 $$$A$$$ 转换为矩阵 $$$B$$$。
操作示例
由于可能需要大量操作,因此请您为 Nastya 回答这个问题。
矩阵 $$$M$$$ 的方子矩阵是由来自矩阵 $$$M$$$ 的索引为 $$$x, x+1, \dots, x+k-1$$$ 的行之一以及来自矩阵的索引为 $$$y, y+1, \dots, y+k-1$$$ 的列之一的所有元素组成的矩阵$$$M$$$。 $$$k$$$ 是方形子矩阵的大小。换句话说,正方形子矩阵是形成实心正方形(即没有孔)的源矩阵元素的集合。
输入
第一行包含两个以空格分隔的整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 500$$$) - 分别是 $$$A$$$ 和 $$$B$$$ 中的行数和列数。
接下来的 $$$n$$$ 行包含 $$$m$$$ 整数,这些行中第 $$$i$$$ 中的第 $$$j$$$ 数字表示矩阵 $$$A$$$ 第 $$$i$$$ 行的第 $$$j$$$ 元素 ($$$1 \leq A_{ij} \leq 10^{9}$$$)。
接下来的 $$$n$$$ 行包含 $$$m$$$ 整数,这些行中第 $$$i$$$ 中的第 $$$j$$$ 数字表示矩阵 $$$B$$$ 第 $$$i$$$ 行的第 $$$j$$$ 元素 ($$$1 \leq B_{ij} \leq 10^{9}$$$)。
输出
如果可以将 $$$A$$$ 转换为 $$$B$$$,则打印“YES”(不带引号),否则打印“NO”(不带引号)。
您可以以任何大小写(大写或小写)打印每个字母。
示例
输入 #1
2 2 1 1 6 1 1 6 1 1
输出 #1
YES
输入 #2
2 2 4 4 4 5 5 4 4 4
输出 #2
NO
输入 #3
3 3 1 2 3 4 5 6 7 8 9 1 4 7 2 5 6 3 8 9
输出 #3
YES
注意
考虑第三个例子。矩阵 $$$A$$$ 最初看起来如下。
$$$$$$ \begin{bmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{bmatrix} $$$$$$
然后我们选择整个矩阵作为转置子矩阵,它变成
$$$$$$ \begin{bmatrix} 1 & 4 & 7\\ 2 & 5 & 8\\ 3 & 6 & 9 \end{bmatrix} $$$$$$
然后我们转置单元格 $$$(2, 2)$$$ 和 $$$(3, 3)$$$ 中带有角点的子矩阵。
$$$$$$ \begin{bmatrix} 1 & 4 & 7\\ 2 & \textbf{5} & \textbf{8}\\ 3 & \textbf{6} & \textbf{9} \end{bmatrix} $$$$$$
所以矩阵变成
$$$$$$ \begin{bmatrix} 1 & 4 & 7\\ 2 & 5 & 6\\ 3 & 8 & 9 \end{bmatrix} $$$$$$
是$$$B$$$。