#CW1. 整除(divide)

整除(divide)

题目描述

现有 2n2n 个正整数,它们构成了一个 2×n2 \times n 的矩形表格。可以将它们在这个矩形表格中任意重新排列。

要求表格中任意两个相邻位置上的整数之和都不能被 33 整除。两个位置相邻,当且仅当它们:

  • 位于同一行且左右相邻;或
  • 位于同一列且上下相邻。

请判断是否存在一种排列方案,使所有相邻位置均满足上述条件。

输入格式

输入包含多组测试数据。

第一行包含一个整数 tt(1≤t≤2001 \le t \le 200),表示测试数据的组数。

对于每组测试数据:

  • 第一行包含一个整数 nn(1≤n≤100001 \le n \le 10000),表示表格的列数;
  • 接下来两行各包含 nn 个正整数,表示待重新排列的全部 2n2n 个整数。

所有整数均小于 10610^6。

输出格式

对于每组测试数据:

  • 如果存在满足条件的排列方案,输出 YES;
  • 否则输出 NO。

样例 1 输入

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

样例 1 输出

YES
NO
YES
YES
YES
NO

数据范围

对于所有测试数据,保证 1≤t≤2001 \le t \le 200,1≤n≤1041 \le n \le 10^4,表格元素不超过 10610^6。

测试点 n≤n \le t≤t \le 特殊性质
1∼31 \sim 3 44 1010 无
4∼94 \sim 9 5050
10∼1210 \sim 12 10001000
13∼1513 \sim 15 10410^4 200200 表格中不存在 33 的倍数
16∼2016 \sim 20 无