题目描述

Masha 有 $n$ 种 $2 \times 2$ 的瓷砖。每块瓷砖的每个格子里都写有一个整数。Masha 拥有每种类型的瓷砖数量无限。

Masha 决定用这些瓷砖拼出一个 $m \times m$ 的正方形。这个正方形需要满足以下条件：它是关于主对角线对称的矩阵；正方形的每个格子都恰好被一块瓷砖的一个格子覆盖；瓷砖的边必须与正方形的边平行；所有瓷砖不能相互重叠；每块瓷砖都必须完全放在正方形内部。具体可参考题目下方的图片说明。

关于主对角线对称的矩阵，指的是对于每一对 $(i, j)$，都有 $s[i][j] = s[j][i]$。也就是说，第 $i$ 行第 $j$ 列的元素等于第 $j$ 行第 $i$ 列的元素。

你的任务是判断 Masha 能否用她拥有的瓷砖拼出一个 $m \times m$ 的主对角线对称矩阵。Masha 可以任意使用每种类型的瓷砖任意多次，但不能旋转瓷砖，只能按输入给定的朝向放置。

你需要回答 $t$ 组独立的测试用例。

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来是 $t$ 组测试用例。

每组测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 100$，$1 \le m \le 100$），分别表示瓷砖类型的数量和 Masha 想要拼出的正方形的边长。

接下来的 $2n$ 行描述了每种瓷砖的具体样式。每种瓷砖连续用两行描述。

描述的第一行包含两个正整数（大于零且不超过 $100$），分别是当前瓷砖左上角和右上角的数字。第二行包含两个正整数（大于零且不超过 $100$），分别是当前瓷砖左下角和右下角的数字。

禁止旋转瓷砖，只允许按输入给定的朝向放置。

输出格式

对于每组测试用例，输出一行答案：如果 Masha 能拼出一个 $m \times m$ 的主对角线对称矩阵，输出 "YES"（不带引号）；否则输出 "NO"（不带引号）。

说明/提示

输入的第一个测试用例有三种类型的瓷砖，如下图所示。

Masha 可以用这些瓷砖拼出如下的 $4 \times 4$ 主对角线对称矩阵：

由 ChatGPT 4.1 翻译

样例

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

YES
NO
YES
NO
YES
YES