1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

struct DisjointSkip {
    vector<int> parent;
    DisjointSkip() {}
    explicit DisjointSkip(int n) : parent(n) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
    void skip_to(int x, int y) { parent[x] = y; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        long long m; int n;
        cin >> m >> n;

        vector<pair<long long,long long>> arcs;
        arcs.reserve(2LL * n);

        for (int i = 0; i < n; ++i) {
            long long x, y; cin >> x >> y;
            if (x <= y) {
                arcs.emplace_back(x, y);
                arcs.emplace_back(x + m, y + m);
            } else {
                arcs.emplace_back(x, y + m);
            }
        }

        if ((long long)n > m) { cout << "NO\n"; continue; }

        // 좌표압축 (실제 좌표값 보존용 배열)
        vector<long long> coords; coords.reserve(2 * arcs.size() + 1);
        coords.push_back(-1); // 경계 안정화를 위한 센티넬
        for (auto &p : arcs) { coords.push_back(p.first); coords.push_back(p.second); }
        sort(coords.begin(), coords.end());
        coords.erase(unique(coords.begin(), coords.end()), coords.end());

        auto get_idx = [&](long long v) -> int {
            return int(lower_bound(coords.begin(), coords.end(), v) - coords.begin());
        };

        // 압축된 인덱스로 치환 후 y 오름차순, x 내림차순 정렬
        vector<pair<int,int>> segs; segs.reserve(arcs.size());
        for (auto &p : arcs) segs.emplace_back(get_idx(p.first), get_idx(p.second));
        sort(segs.begin(), segs.end(), [&](const auto& a, const auto& b) {
            if (a.second != b.second) return a.second < b.second;
            return a.first > b.first;
        });

        const int S = (int)coords.size();
        DisjointSkip leftRoot(S + 2), rightNext(S + 2);
        vector<long long> addCount(S + 2, 0);

        auto find_left = [&](int x) { return leftRoot.find(x); };
        auto find_right = [&](int x) { return rightNext.find(x); };

        bool ok = true;
        for (const auto& rg : segs) {
            int a = rg.first, b = rg.second;

            int rootA = find_left(a);
            addCount[rootA] += 1; // 효과적으로 "k ≤ a"에 +1이 들어가도록 후보를 루트에 모읍니다

            // 오른쪽 후보가 지배되면 병합 (nxt ≤ b+1까지만 의미 있음)
            while (true) {
                int nxt = find_right(rootA + 1);
                if (nxt > b + 1) break;
                int nxt2 = find_right(nxt + 1);
                if (coords[rootA] + addCount[rootA] >= coords[nxt]) {
                    leftRoot.skip_to(nxt, rootA);
                    rightNext.skip_to(nxt, nxt2);
                    addCount[rootA] += addCount[nxt];
                } else {
                    break;
                }
            }

            // Hall 검사: max_k (k + cnt[k]) ≤ y + 1
            int rb = find_left(b);
            if (coords[rb] + addCount[rb] > coords[b] + 1) {
                ok = false;
                break;
            }
        }

        cout << (ok ? "YES\n" : "NO\n");
    }
    return 0;
}