Code : Penacony

#include <bits/stdc++.h>
using namespace std;

class LazySegtree {
    int n;
    vector<int> a;

  public:
    LazySegtree(int n) {
        this->n = n;
        a.resize(n);
    }

    void add(int l, int r, int delta) {
        if (l > r) {
            return;
        }
        for (int i = l; i <= r; i++) {
            a[i] += delta;
        }
    }

    int query_freq_of_min(int l, int r) {
        int mn = a[l];
        for (int i = l; i <= r; i++) {
            mn = min(mn, a[i]);
        }
        int freq = 0;
        for (int i = l; i <= r; i++) {
            freq += (a[i] == mn);
        }
        return freq;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;

    LazySegtree st(n);

    vector<vector<int>> adj(n);
    map<pair<int, int>, bool> is_crossover;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        st.add(x, y - 1, 1);
        adj[x].push_back(y);
        adj[y].push_back(x);
        is_crossover[{x, y}] = false;
    }

    int ans = n;

    // Before the loop, edge (n - 1, 0) is deleted, that is why there are no
    // crossovers initially.
    //
    // In each iteration, delete edge (x, x + 1)
    for (int x = 0; x < n - 1; x++) {
        // All edges which have one endpoint as x will flip orientation.
        for (auto y : adj[x]) {
            int L = min(x, y), R = max(x, y);
            if (!is_crossover[{L, R}]) {
                // Delete the old contribution.
                st.add(L, R - 1, -1);

                // Add the new contribution.
                st.add(R, n - 1, 1);
                st.add(0, L - 1, 1);
            } else {
                // Delete the old contribution.
                st.add(R, n - 1, -1);
                st.add(0, L - 1, -1);

                // Add the new contribution.
                st.add(L, R - 1, 1);
            }

            is_crossover[{L, R}] = !is_crossover[{L, R}];
        }
        ans = min(ans, n - st.query_freq_of_min(0, n - 1));
    }

    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
    return 0;
}

#include <atcoder/lazysegtree>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

// S is used for querying minimum element and its frequency.
// (ele, freq)
using S = pair<int, int>;

// op is used for querying.
S op(S a, S b) {
    // If the minimum in both half is equal, frequency will be summed up.
    if (a.first == b.first) {
        return {a.first, a.second + b.second};
    }

    return min(a, b);
}

S e() { return {1e9, 0}; }

// F is used for performing range updates.
using F = int;

F composition(F l, F r) { return l + r; }

F id() { return 0; }

// mapping should return f(x). How does S change when you apply the composition
// on it.
// If you add f to an (ele, freq), it will change to (ele + f, freq)
S mapping(F f, S x) { return {f + x.first, x.second}; }

class LazySegtree {
    int n;
    lazy_segtree<S, op, e, F, mapping, composition, id> *st;

  public:
    LazySegtree(int n) {
        vector<S> initial(n, S{0, 1});
        this->n = n;
        st = new lazy_segtree<S, op, e, F, mapping, composition, id>(initial);
    }

    void add(int l, int r, int delta) {
        if (l > r) {
            return;
        }
        // Atcoder's segtree has [close, open) range.
        st->apply(l, r + 1, delta);
    }

    int query_freq_of_min(int l, int r) { return st->prod(l, r + 1).second; }
};

void solve() {
    int n, m;
    cin >> n >> m;

    LazySegtree st(n);

    vector<vector<int>> adj(n);
    map<pair<int, int>, bool> is_crossover;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        st.add(x, y - 1, 1);
        adj[x].push_back(y);
        adj[y].push_back(x);
        is_crossover[{x, y}] = false;
    }

    int ans = n;

    // Before the loop, edge (n - 1, 0) is deleted, that is why there are no
    // crossovers initially.
    //
    // In each iteration, delete edge (x, x + 1)
    for (int x = 0; x < n - 1; x++) {
        // All edges which have one endpoint as x will flip orientation.
        for (auto y : adj[x]) {
            int L = min(x, y), R = max(x, y);
            if (!is_crossover[{L, R}]) {
                // Delete the old contribution.
                st.add(L, R - 1, -1);

                // Add the new contribution.
                st.add(R, n - 1, 1);
                st.add(0, L - 1, 1);
            } else {
                // Delete the old contribution.
                st.add(R, n - 1, -1);
                st.add(0, L - 1, -1);

                // Add the new contribution.
                st.add(L, R - 1, 1);
            }

            is_crossover[{L, R}] = !is_crossover[{L, R}];
        }
        ans = min(ans, n - st.query_freq_of_min(0, n - 1));
    }

    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
    return 0;
}