#P4354. Magic cube

    ID: 3560 传统题 1000ms 512MiB 尝试: 20 已通过: 6 难度: 8 上传者: 标签>难度分类提高+/省选-线性代数与代数群构造与建模奇偶性分析不变量分析数据结构树状数组排序与序列处理离散化CF2400

Magic cube

Magic cube

题目描述

莱因斯坦迷上了一种叫作二维魔方的游戏。魔方是一个 N×NN\times N 的方格矩阵,每个方格有一种颜色。

二维魔方的初始状态

一次操作可以将任意一行向左或向右循环移动,也可以将任意一列向上或向下循环移动。移出的一端的方格会按原来的顺序从另一端进入。下图是将上图的第二行向右移动两个位置的结果。

第二行向右循环移动两个位置后的二维魔方

给定魔方的初始状态和目标状态,判断能否通过上述操作使魔方达到目标状态。

输入格式

第一行一个整数 TT,表示数据组数。

每组数据的第一行有一个整数 NN,表示魔方的边长。接下来 NN 行给出初始状态,再接下来 NN 行给出目标状态。每行有 NN 个整数,表示各格的颜色。不同整数表示不同颜色。

输出格式

每组数据输出一行。如果可以达到目标状态,输出 Yes;否则输出 No。

样例

样例输入 #1

2
3
1 2 3
4 5 6
7 8 9
2 1 3
4 5 6
7 8 9
6
1 1 2 3 3 4
4 1 1 4 2 3
3 3 1 1 1 4
3 4 4 3 4 3
4 3 4 4 3 3
3 3 3 3 4 2
1 1 2 3 3 3
2 3 4 1 1 2
3 3 1 1 1 4
3 4 4 3 4 4
4 3 4 4 3 4
3 3 3 3 4 3

样例输出 #1

No
Yes

数据范围

1≤T≤151\le T\le 15,1≤N≤501\le N\le 50。