<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

474. All for Love
Time limit per test: 1.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Masha has already tried all traditional ways to attract attention of Misha. The last chance to win the desired man is to use magic. And the most suitable moment to use magic is Halloween evening. To summon dark forces she bought large magic plate and a set of small plates. Every plate has a form of the right isosceles triangle. To achieve a magic effect, one need to completely cover the large plate with small ones. Moreover, every small plate should be placed in such a way that each of it's cathetuses is parallel to some cathetus of the large plate. To make the process of covering easier, an instruction is included into magic collection. Instruction says: let's introduce coordinate system in such a way that the large plate will become a triangle with vertices in (0, 0), (0, n) and (n, 0). Then the instruction gives the exact position of every small plate in this coordinate system. Masha carefully followed this instruction and constructed the coverage. But she is still in doubt: what if the instruction is wrong and all efforts are useless? This question gives her no sleep, and she asks you to verify the instruction. More formally, let's call a coverage of the large triangle by small triangles correct if all the following conditions hold:
all triangles are right and isosceles,
no two triangles cross,
every triangle is inside the large one,
every part of the large triangle is covered by some small triangle.

An example of the correct coverage.

Input
Input consits of several test cases. The first line contains one positive integer t ≤ 10 — the number of test cases. Every case starts with a line with two integers n and m — the length of the large triangle's cathetus and the number of small triangles in the coverage correspondingly (1 ≤ n ≤ 25000, 1 ≤ m ≤ 100000). The rest of the test case consists of m lines containing 6 non-negative integers each: x1, y1, x2, y2, x3, y3, which denote the coordinates of vertices of the small triangles. These numbers don't exceed 25000. Every triangle is guaranteed to be nondegenerate. Total number of triangles in all test cases doesn't exceed 200000.

Output
For every test case output one line with a word "YES", if the given coverage is correct, and "NO" otherwise.

Example(s)
sample input
sample output
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

<|response|>
## 1. Abridged problem statement

Given a large right isosceles triangle with vertices:

```text
(0, 0), (0, n), (n, 0)
```

and `m` smaller triangles described by integer coordinates, determine whether the small triangles form a correct covering of the large triangle.

A covering is correct if:

1. every small triangle is right isosceles;
2. each small triangle's catheti are horizontal/vertical;
3. every small triangle lies inside the large triangle;
4. no two small triangles overlap improperly;
5. the whole large triangle is covered.

For each test case, output `"YES"` or `"NO"`.

---

## 2. Key observations needed to solve the problem

### Observation 1: The large triangle is simple to test

The large triangle consists of all points satisfying:

```text
x >= 0
y >= 0
x + y <= n
```

Its doubled area is:

```text
n²
```

We use doubled areas to avoid floating-point computations.

---

### Observation 2: Valid small triangles have only four edge directions

If a small triangle is right isosceles and its catheti are parallel to the large triangle's catheti, then:

- one cathetus is horizontal;
- one cathetus is vertical;
- the hypotenuse has slope `+1` or `-1`.

So every edge has one of four directions:

```text
horizontal
vertical
diagonal slope +1
diagonal slope -1
```

---

### Observation 3: Area equality is necessary but not sufficient

The sum of areas of all small triangles must equal the area of the large triangle.

However, this alone does not guarantee a valid covering, because triangles could overlap and leave holes elsewhere.

So we also need a local geometric consistency check.

---

### Observation 4: Use angle sums at vertices

At every relevant point, the total angle covered by small triangles must equal the angle of the large triangle at that point.

Expected angle:

| Point position | Expected angle |
|---|---:|
| `(0, 0)` | `90°` |
| `(n, 0)` or `(0, n)` | `45°` |
| On boundary but not a corner | `180°` |
| Strictly inside | `360°` |

Each valid small triangle contributes:

- `90°` at its right-angle vertex;
- `45°` at each acute vertex.

---

### Observation 5: Handle T-junctions

A vertex of one triangle may lie strictly inside an edge of another triangle:

```text
A ----- P ----- B
```

At point `P`, the edge `AB` contributes an additional straight angle:

```text
180°
```

Therefore, for every input vertex, we must count how many triangle edges strictly contain it.

---

### Observation 6: T-junctions can be found with 1D sweeps

Since edges have only four possible directions, for each direction we can project everything onto a line and solve interval stabbing.

For every direction:

| Direction | Line level | Position |
|---|---|---|
| Horizontal | `y` | `x` |
| Vertical | `x` | `y` |
| Slope `+1` | `y - x` | `x` |
| Slope `-1` | `x + y` | `x` |

For each line level:

- every edge becomes an interval `[lo, hi]`;
- every vertex becomes a query point.

We need to know how many intervals strictly contain each query point.

Use sweep events:

| Type | Meaning |
|---:|---|
| `0` | edge closes |
| `1` | vertex query |
| `2` | edge opens |

Sorting by:

```text
level, position, type
```

with order:

```text
close < query < open
```

ensures endpoints are not counted as being strictly inside an edge.

---

## 3. Full solution approach

For each test case:

### Step 1: Validate every small triangle

For each triangle, try each vertex as the right-angle vertex.

For a candidate right-angle vertex `A`, with other vertices `B` and `C`, define vectors:

```text
AB = B - A
AC = C - A
```

The triangle is valid if:

```text
AB · AC = 0
|AB|² = |AC|²
AB and AC are horizontal/vertical
```

Also verify each vertex lies inside the large triangle:

```text
x >= 0
y >= 0
x + y <= n
```

---

### Step 2: Check total area

Compute doubled area of each triangle using cross product:

```text
area2 = abs((B - A) × (C - A))
```

The sum must be exactly:

```text
n²
```

If not, answer is `"NO"`.

---

### Step 3: Compress all triangle vertices

Collect all input vertices and assign each unique point an integer id.

We will store the accumulated angle contribution for each unique vertex.

---

### Step 4: Add direct triangle angle contributions

For each valid triangle:

- add `90` to its right-angle vertex;
- add `45` to its other two vertices.

---

### Step 5: Add T-junction angle contributions

For each of the four edge directions:

1. Convert every edge of that direction into an interval.
2. Convert every unique vertex into a query.
3. Sort all events by `(level, position, type)`.
4. Sweep each line level independently.
5. At every query, add:

```text
180 * active_intervals
```

to that vertex's angle sum.

Because of event order `close < query < open`, a vertex equal to an edge endpoint is not counted as lying inside that edge.

---

### Step 6: Compare with expected angles

For every unique input vertex:

- expected angle is determined by its position in the large triangle;
- compare with accumulated angle.

If all match, output `"YES"`, otherwise `"NO"`.

---

### Complexity

Let `V <= 3m` be the number of unique vertices.

For each of 4 directions we sort `O(m + V)` events.

Total complexity:

```text
O((m + V) log(m + V))
```

Memory complexity:

```text
O(m + V)
```

---

## 4. C++ implementation with comments

```cpp
#include <bits/stdc++.h>
// #include <coding_library/geometry/point.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

using coord_t = double;

struct Point {
    static constexpr coord_t eps = 1e-9;
    static inline const coord_t PI = acos((coord_t)-1.0);

    coord_t x, y;
    Point(coord_t x = 0, coord_t y = 0) : x(x), y(y) {}

    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(coord_t c) const { return Point(x * c, y * c); }
    Point operator/(coord_t c) const { return Point(x / c, y / c); }

    coord_t operator*(const Point& p) const { return x * p.x + y * p.y; }
    coord_t operator^(const Point& p) const { return x * p.y - y * p.x; }

    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
    bool operator!=(const Point& p) const { return x != p.x || y != p.y; }
    bool operator<(const Point& p) const {
        return x != p.x ? x < p.x : y < p.y;
    }
    bool operator>(const Point& p) const {
        return x != p.x ? x > p.x : y > p.y;
    }
    bool operator<=(const Point& p) const {
        return x != p.x ? x < p.x : y <= p.y;
    }
    bool operator>=(const Point& p) const {
        return x != p.x ? x > p.x : y >= p.y;
    }

    coord_t norm2() const { return x * x + y * y; }
    coord_t norm() const { return sqrt(norm2()); }
    coord_t angle() const { return atan2(y, x); }

    Point rotate(coord_t a) const {
        return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }

    Point perp() const { return Point(-y, x); }
    Point unit() const { return *this / norm(); }
    Point normal() const { return perp().unit(); }
    Point project(const Point& p) const {
        return *this * (*this * p) / norm2();
    }
    Point reflect(const Point& p) const {
        return *this * 2 * (*this * p) / norm2() - p;
    }

    friend ostream& operator<<(ostream& os, const Point& p) {
        return os << p.x << ' ' << p.y;
    }
    friend istream& operator>>(istream& is, Point& p) {
        return is >> p.x >> p.y;
    }

    friend int ccw(const Point& a, const Point& b, const Point& c) {
        coord_t v = (b - a) ^ (c - a);
        if(-eps <= v && v <= eps) {
            return 0;
        } else if(v > 0) {
            return 1;
        } else {
            return -1;
        }
    }

    friend bool point_on_segment(
        const Point& a, const Point& b, const Point& p
    ) {
        return ccw(a, b, p) == 0 && p.x >= min(a.x, b.x) - eps &&
               p.x <= max(a.x, b.x) + eps && p.y >= min(a.y, b.y) - eps &&
               p.y <= max(a.y, b.y) + eps;
    }

    friend bool point_in_triangle(
        const Point& a, const Point& b, const Point& c, const Point& p
    ) {
        int d1 = ccw(a, b, p);
        int d2 = ccw(b, c, p);
        int d3 = ccw(c, a, p);
        return (d1 >= 0 && d2 >= 0 && d3 >= 0) ||
               (d1 <= 0 && d2 <= 0 && d3 <= 0);
    }

    friend Point line_line_intersection(
        const Point& a1, const Point& b1, const Point& a2, const Point& b2
    ) {
        return a1 +
               (b1 - a1) * ((a2 - a1) ^ (b2 - a2)) / ((b1 - a1) ^ (b2 - a2));
    }

    friend bool collinear(const Point& a, const Point& b) {
        return abs(a ^ b) < eps;
    }

    friend Point circumcenter(const Point& a, const Point& b, const Point& c) {
        Point mid_ab = (a + b) / 2.0;
        Point mid_ac = (a + c) / 2.0;
        Point perp_ab = (b - a).perp();
        Point perp_ac = (c - a).perp();
        return line_line_intersection(
            mid_ab, mid_ab + perp_ab, mid_ac, mid_ac + perp_ac
        );
    }

    friend coord_t arc_area(
        const Point& center, coord_t r, const Point& p1, const Point& p2
    ) {
        coord_t theta1 = (p1 - center).angle();
        coord_t theta2 = (p2 - center).angle();
        if(theta2 < theta1 - eps) {
            theta2 += 2 * PI;
        }

        coord_t d_theta = theta2 - theta1;
        coord_t cx = center.x, cy = center.y;
        coord_t area = r * cx * (sin(theta2) - sin(theta1)) -
                       r * cy * (cos(theta2) - cos(theta1)) + r * r * d_theta;
        return area / 2.0;
    }

    friend vector<Point> intersect_circles(
        const Point& c1, coord_t r1, const Point& c2, coord_t r2
    ) {
        Point d = c2 - c1;
        coord_t dist = d.norm();

        if(dist > r1 + r2 + eps || dist < abs(r1 - r2) - eps || dist < eps) {
            return {};
        }

        coord_t a = (r1 * r1 - r2 * r2 + dist * dist) / (2 * dist);
        coord_t h_sq = r1 * r1 - a * a;
        if(h_sq < -eps) {
            return {};
        }
        if(h_sq < 0) {
            h_sq = 0;
        }
        coord_t h = sqrt(h_sq);

        Point mid = c1 + d.unit() * a;
        Point perp_dir = d.perp().unit();

        if(h < eps) {
            return {mid};
        }
        return {mid + perp_dir * h, mid - perp_dir * h};
    }

    friend optional<Point> intersect_ray_segment(
        const Point& ray_start, const Point& ray_through, const Point& seg_a,
        const Point& seg_b
    ) {
        Point ray_dir = ray_through - ray_start;
        if(ray_dir.norm2() < Point::eps) {
            return {};
        }
        Point seg_dir = seg_b - seg_a;
        coord_t denom = ray_dir ^ seg_dir;
        if(fabs(denom) < eps) {
            return {};
        }
        coord_t t = ((seg_a - ray_start) ^ seg_dir) / denom;
        if(t < eps) {
            return {};
        }
        coord_t s = ((seg_a - ray_start) ^ ray_dir) / denom;
        if(s < eps || s > 1 - eps) {
            return {};
        }
        return ray_start + ray_dir * t;
    }
};

namespace fast_in {
static char buf[1 << 22];
static int bp = 0, blen = 0;
static inline int gc() {
    if(bp == blen) {
        blen = (int)fread(buf, 1, sizeof(buf), stdin);
        bp = 0;
        if(blen == 0) {
            return -1;
        }
    }
    return buf[bp++];
}
static inline int ri() {
    int c = gc();
    while(c != -1 && c <= ' ') {
        c = gc();
    }
    int x = 0;
    while(c > ' ') {
        x = x * 10 + c - '0';
        c = gc();
    }
    return x;
}
}  // namespace fast_in

int n, m;
vector<array<Point, 3>> triangles;

int right_angle_index(const array<Point, 3>& t) {
    for(int i = 0; i < 3; i++) {
        int j = (i + 1) % 3, k = (i + 2) % 3;
        Point u = t[j] - t[i];
        Point v = t[k] - t[i];
        if(u * v == 0 && u.norm2() == v.norm2()) {
            bool axis_aligned =
                (u.x == 0 || u.y == 0) && (v.x == 0 || v.y == 0);
            if(axis_aligned) {
                return i;
            }
        }
    }
    return -1;
}

bool inside_large(const Point& p) {
    return p.x >= 0 && p.y >= 0 && p.x + p.y <= n;
}

void read() {
    n = fast_in::ri();
    m = fast_in::ri();
    triangles.assign(m, {});
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < 3; j++) {
            triangles[i][j].x = fast_in::ri();
            triangles[i][j].y = fast_in::ri();
        }
    }
}

void solve() {
    // For a valid tiling, at every unique vertex V the angles of the
    // triangles touching V must fill the locally-interior region exactly:
    // 360 deg strictly inside the large triangle, 180 deg along a boundary
    // edge, 90 deg at (0, 0), and 45 deg at (n, 0) and (0, n). Per triangle
    // we credit 90 deg at its right-angle vertex and 45 deg at each acute
    // vertex. A vertex that lies strictly in the interior of some other
    // triangle's edge (a T-junction) picks up another 180 deg from that
    // edge passing straight through it. So the entire check reduces to
    // computing this angle sum per unique vertex and matching it against
    // the expected value above.
    //
    // The only nontrivial part is detecting T-junctions efficiently. Edges
    // come in just four direction classes - horizontal, vertical, slope +1,
    // slope -1 - because catheti are axis-aligned and forces hypotenuses
    // onto a +/-45 deg diagonal. For each direction d we group everything
    // by the constant coordinate of the line supporting an edge in that
    // direction, called the "level":
    //
    //   d = 0 (horizontal):   level = y,      pos = x
    //   d = 1 (vertical):     level = x,      pos = y
    //   d = 2 (slope +1):     level = y - x,  pos = x
    //   d = 3 (slope -1):     level = x + y,  pos = x
    //
    // Within one level the problem becomes 1D: each edge is an interval
    // [lo, hi] in pos, each vertex is a point in pos, and we need to
    // know, for every vertex, how many edge intervals strictly contain it.
    //
    // We emit three event kinds, sorted by (level, pos, type):
    //
    //   type 2 - edge opens at its lower endpoint
    //   type 1 - vertex query
    //   type 0 - edge closes at its upper endpoint
    //
    // The tie-break order at equal (level, pos) is close < query < open,
    // so that an edge ending at a position is removed before any vertex
    // sitting on that position is queried, and an edge starting at a
    // position is added only after queries at the same position. Both
    // ensure a vertex coinciding with an edge endpoint is never counted
    // as being in that edge's interior.
    //
    // We sweep through the events one level at a time, maintaining a
    // counter of currently-open intervals. At each vertex query the
    // counter equals the number of edges in direction d whose interior
    // contains the vertex, and we credit 180 deg per such edge. Repeating
    // this for all four directions gives the full T-junction contribution.
    //
    // We also verify each triangle is right isosceles with axis-aligned
    // catheti, sits inside the large triangle, and that the total area
    // equals n^2 / 2.

    vector<int> right_idx(m);
    coord_t total_area_x2 = 0;
    for(int i = 0; i < m; i++) {
        int r = right_angle_index(triangles[i]);
        if(r < 0) {
            cout << "NO\n";
            return;
        }
        right_idx[i] = r;
        for(int j = 0; j < 3; j++) {
            if(!inside_large(triangles[i][j])) {
                cout << "NO\n";
                return;
            }
        }
        total_area_x2 +=
            abs((triangles[i][1] - triangles[i][0]) ^
                (triangles[i][2] - triangles[i][0]));
    }

    if(total_area_x2 != (coord_t)n * n) {
        cout << "NO\n";
        return;
    }

    vector<array<int, 6>> tri_int(m);
    vector<pair<int, int>> all_pts;
    all_pts.reserve(3 * m);
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < 3; j++) {
            int x = (int)triangles[i][j].x, y = (int)triangles[i][j].y;
            tri_int[i][2 * j] = x;
            tri_int[i][2 * j + 1] = y;
            all_pts.push_back({x, y});
        }
    }
    sort(all_pts.begin(), all_pts.end());
    all_pts.erase(unique(all_pts.begin(), all_pts.end()), all_pts.end());
    int V = (int)all_pts.size();

    vector<array<int, 3>> tri_vid(m);
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < 3; j++) {
            pair<int, int> key = {tri_int[i][2 * j], tri_int[i][2 * j + 1]};
            tri_vid[i][j] =
                (int)(lower_bound(all_pts.begin(), all_pts.end(), key) -
                      all_pts.begin());
        }
    }

    vector<int64_t> angle_at(V, 0);
    for(int i = 0; i < m; i++) {
        int r = right_idx[i];
        angle_at[tri_vid[i][r]] += 90;
        angle_at[tri_vid[i][(r + 1) % 3]] += 45;
        angle_at[tri_vid[i][(r + 2) % 3]] += 45;
    }

    // Packed event key, sortable as one uint64. Layout (high to low bits):
    //   level (signed, shifted): 18 bits  -> [-65536, 65535] range
    //   pos:                     17 bits  -> [0, 131071]
    //   type:                     2 bits  -> 0 = close, 1 = query, 2 = open
    //   vid + 1:                 20 bits  -> 0 means "no vid"
    auto pack = [](int level, int pos, int type, int vid) -> uint64_t {
        uint64_t lv = (uint64_t)(level + (1 << 17));
        return (lv << 39) | ((uint64_t)pos << 22) | ((uint64_t)type << 20) |
               (uint64_t)(vid + 1);
    };

    struct DirInfo {
        int level, pos;
    };
    auto level_pos = [](int d, int x, int y) -> DirInfo {
        if(d == 0) {
            return {y, x};
        }
        if(d == 1) {
            return {x, y};
        }
        if(d == 2) {
            return {y - x, x};
        }
        return {x + y, x};
    };

    auto edge_direction = [](int dx, int dy) -> int {
        if(dy == 0) {
            return 0;
        }
        if(dx == 0) {
            return 1;
        }
        if(dx == dy) {
            return 2;
        }
        return 3;
    };

    vector<uint64_t> events;
    events.reserve(6 * m + V);
    for(int d = 0; d < 4; d++) {
        events.clear();
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < 3; j++) {
                int ax = tri_int[i][2 * j], ay = tri_int[i][2 * j + 1];
                int bx = tri_int[i][2 * ((j + 1) % 3)],
                    by = tri_int[i][2 * ((j + 1) % 3) + 1];
                if(edge_direction(bx - ax, by - ay) != d) {
                    continue;
                }
                DirInfo a = level_pos(d, ax, ay), b = level_pos(d, bx, by);
                int lo = min(a.pos, b.pos), hi = max(a.pos, b.pos);
                events.push_back(pack(a.level, lo, 2, -1));
                events.push_back(pack(a.level, hi, 0, -1));
            }
        }
        for(int v = 0; v < V; v++) {
            DirInfo lp = level_pos(d, all_pts[v].first, all_pts[v].second);
            events.push_back(pack(lp.level, lp.pos, 1, v));
        }

        sort(events.begin(), events.end());

        int prev_level = INT_MIN;
        int active = 0;
        for(uint64_t e: events) {
            int level = (int)(e >> 39) - (1 << 17);
            int type = (int)((e >> 20) & 3);
            int vid_plus_one = (int)(e & ((1u << 20) - 1));
            if(level != prev_level) {
                prev_level = level;
                active = 0;
            }
            if(type == 0) {
                active--;
            } else if(type == 1) {
                angle_at[vid_plus_one - 1] += 180LL * active;
            } else {
                active++;
            }
        }
    }

    for(int v = 0; v < V; v++) {
        int x = all_pts[v].first, y = all_pts[v].second;
        int64_t a = angle_at[v];
        int64_t expected;
        if(x == 0 && y == 0) {
            expected = 90;
        } else if((x == n && y == 0) || (x == 0 && y == n)) {
            expected = 45;
        } else if(x == 0 || y == 0 || x + y == n) {
            expected = 180;
        } else {
            expected = 360;
        }
        if(a != expected) {
            cout << "NO\n";
            return;
        }
    }

    cout << "YES\n";
}

int main() {
    int T = fast_in::ri();
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5. Python implementation with comments

```python
import sys


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    ptr = 0

    T = data[ptr]
    ptr += 1

    answers = []

    VID_BITS = 20
    TYPE_SHIFT = VID_BITS
    POS_SHIFT = VID_BITS + 2
    LEVEL_SHIFT = POS_SHIFT + 17
    LEVEL_OFFSET = 1 << 17
    VID_MASK = (1 << VID_BITS) - 1

    def pack(level, pos, typ, vid):
        return (
            ((level + LEVEL_OFFSET) << LEVEL_SHIFT)
            | (pos << POS_SHIFT)
            | (typ << TYPE_SHIFT)
            | (vid + 1)
        )

    def inside_large(p, n):
        x, y = p
        return x >= 0 and y >= 0 and x + y <= n

    def dot(a, b, c):
        x1 = b[0] - a[0]; y1 = b[1] - a[1]
        x2 = c[0] - a[0]; y2 = c[1] - a[1]
        return x1 * x2 + y1 * y2

    def dist2(a, b):
        dx = b[0] - a[0]; dy = b[1] - a[1]
        return dx * dx + dy * dy

    def cross(a, b, c):
        x1 = b[0] - a[0]; y1 = b[1] - a[1]
        x2 = c[0] - a[0]; y2 = c[1] - a[1]
        return x1 * y2 - y1 * x2

    def axis_aligned(a, b):
        return a[0] == b[0] or a[1] == b[1]

    def right_angle_index(tri):
        for i in range(3):
            j = (i + 1) % 3; k = (i + 2) % 3
            a = tri[i]; b = tri[j]; c = tri[k]
            if dot(a, b, c) != 0: continue
            if dist2(a, b) != dist2(a, c): continue
            if not axis_aligned(a, b): continue
            if not axis_aligned(a, c): continue
            return i
        return -1

    def level_pos(d, x, y):
        if d == 0: return y, x
        if d == 1: return x, y
        if d == 2: return y - x, x
        return x + y, x

    def edge_direction(dx, dy):
        if dy == 0: return 0
        if dx == 0: return 1
        if dx == dy: return 2
        return 3

    for _ in range(T):
        n = data[ptr]; m = data[ptr + 1]; ptr += 2

        triangles = []
        for _i in range(m):
            x1, y1, x2, y2, x3, y3 = data[ptr:ptr + 6]; ptr += 6
            triangles.append(((x1, y1), (x2, y2), (x3, y3)))

        right_idx = [-1] * m
        total_area2 = 0
        ok = True

        for i, tri in enumerate(triangles):
            r = right_angle_index(tri)
            if r < 0:
                ok = False; break
            right_idx[i] = r
            for p in tri:
                if not inside_large(p, n):
                    ok = False; break
            if not ok: break
            total_area2 += abs(cross(tri[0], tri[1], tri[2]))

        if not ok:
            answers.append("NO"); continue

        if total_area2 != n * n:
            answers.append("NO"); continue

        tri_int = []; all_pts_list = []
        for tri in triangles:
            flat = []
            for x, y in tri:
                flat.extend([x, y]); all_pts_list.append((x, y))
            tri_int.append(flat)

        all_pts = sorted(set(all_pts_list))
        V = len(all_pts)
        point_id = {p: i for i, p in enumerate(all_pts)}

        tri_vid = []
        for flat in tri_int:
            ids = []
            for j in range(3):
                p = (flat[2 * j], flat[2 * j + 1])
                ids.append(point_id[p])
            tri_vid.append(ids)

        angle_at = [0] * V
        for i in range(m):
            r = right_idx[i]; ids = tri_vid[i]
            angle_at[ids[r]] += 90
            angle_at[ids[(r + 1) % 3]] += 45
            angle_at[ids[(r + 2) % 3]] += 45

        for d in range(4):
            events = []
            for flat in tri_int:
                for j in range(3):
                    ax = flat[2 * j]; ay = flat[2 * j + 1]
                    nj = (j + 1) % 3
                    bx = flat[2 * nj]; by = flat[2 * nj + 1]
                    if edge_direction(bx - ax, by - ay) != d: continue
                    level_a, pos_a = level_pos(d, ax, ay)
                    level_b, pos_b = level_pos(d, bx, by)
                    lo = min(pos_a, pos_b); hi = max(pos_a, pos_b)
                    events.append(pack(level_a, lo, 2, -1))
                    events.append(pack(level_a, hi, 0, -1))
            for vid, (x, y) in enumerate(all_pts):
                level, pos = level_pos(d, x, y)
                events.append(pack(level, pos, 1, vid))
            events.sort()
            prev_level = None; active = 0
            for e in events:
                level = (e >> LEVEL_SHIFT) - LEVEL_OFFSET
                typ = (e >> TYPE_SHIFT) & 3
                vid_plus_one = e & VID_MASK
                if level != prev_level:
                    prev_level = level; active = 0
                if typ == 0:
                    active -= 1
                elif typ == 1:
                    vid = vid_plus_one - 1
                    angle_at[vid] += 180 * active
                else:
                    active += 1

        for vid, (x, y) in enumerate(all_pts):
            if x == 0 and y == 0:
                expected = 90
            elif (x == n and y == 0) or (x == 0 and y == n):
                expected = 45
            elif x == 0 or y == 0 or x + y == n:
                expected = 180
            else:
                expected = 360
            if angle_at[vid] != expected:
                ok = False; break

        answers.append("YES" if ok else "NO")

    sys.stdout.write("\n".join(answers))


if __name__ == "__main__":
    solve()
```
