题目描述

大魔法板是顶点为 $(0,0),(0,n),(n,0)$ 的直角等腰三角形。现在给出 $m$ 个小三角形的三个顶点坐标，需要判断它们是否构成大三角形的一份正确覆盖。

正确覆盖必须同时满足：

• 每个小三角形都是直角等腰三角形；
• 每个小三角形的两条直角边分别平行于大三角形的两条直角边（即水平/竖直）；
• 所有小三角形都位于大三角形内部或边界上；
• 任意两个小三角形内部不能重叠或交叉；
• 大三角形的每一点都被至少一个小三角形覆盖。

输入格式

第一行一个整数 $t\le10$。

每组数据第一行两个整数 $n,m$，其中 $1\le n\le25000$，$1\le m\le100000$。

接下来 $m$ 行，每行六个非负整数 x1 y1 x2 y2 x3 y3，表示一个小三角形三个顶点；坐标均不超过 25000，且每个输入三角形保证非退化。

所有测试中 $m$ 的总和不超过 200000。

输出格式

每组数据输出 YES 或 NO。

样例

3
1 1
0 0 0 1 1 0
2 3
0 0 1 1 0 1
0 1 1 1 0 2
1 1 2 0 1 0
3 6
0 0 0 1 1 1
0 0 1 0 1 1
1 0 1 1 2 1
1 0 2 0 2 1
2 0 2 1 3 0
0 1 2 1 0 3

YES
NO
YES