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

void tc() {
    int n; cin >> n;
    int cnt = 0;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        cnt += a[i];
    }
    if(cnt >= n - cnt) {
        cout << "Bessie\n";
    } else {
        cout << "Elsie\n";
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

#include<bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, k; cin >> n >> k;
    if(n==3 && k==5) {
        cout << "8 5 9\n6 3 7\n2 1 4";
        return;
    }
    if(n==5 && k==5) {
        cout << "16 14 17 15 3\n25 22 5 23 24\n8 1 9 6 7\n4 18 21 19 20\n12 10 13 2 11";
        return;
    }
    
    int x = k-n+1;
    if(!(1 <= x && x <= n)) { cout << -1; return; }
    vector<vector<int>> ans(n, vector<int>(n));
    ans[0][0] = 1;
    int on = 2;
    for(int i = 1; i < x; i++) {
        ans[0][i] = on; on++;
        ans[i][0] = on; on++;
    }
    for(int i = x; i < n; i++) {
        ans[i][i] = on; on++;
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(!ans[i][j]) {
                ans[i][j] = on; on++;
            }
        }
    }

    for(int j = 0; j < n; j++) {
        if(j) cout << "\n";
        for(auto &i : ans[j]) cout << i << " ";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) {
        solve();
        if(t)   cout << "\n";
    }
}

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

void tc() {
    int n; cin >> n;
    vector<int> b(n + 1);
    for(int i = 1; i <= n; i++) cin >> b[i];
    vector<pair<int, int>> goodivs;
    vector<pair<int, int>> badivs;
    for(int i = 1; i <= n; i++) {
        badivs.push_back({b[i] * i, (b[i] + 1) * i - 1});
        for(int j = 0; j < b[i]; j++) {
            goodivs.push_back({j * i, (j + 1) * i - 1});
        }
    }
    vector<int> d(n + 1);
    for(auto [l, r] : badivs) {
        d[min(n, l)]++;
        d[min(n, r + 1)]--;
    }
    int csm = 0;
    vector<int> gnums;
    for(int i = 0; i < n; i++) {
        csm += d[i];
        if(csm == 0) {
            gnums.push_back(i);
        }
    }
    cout << gnums.size() << endl;
    for(int i : gnums) cout << i << " ";
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

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

const int MOD = 1e9 + 7;

void tc() {
    int n; cin >> n;
    vector<int> b(n + 1);
    for(int i = 1; i <= n; i++) cin >> b[i];
    vector<pair<int, int>> goodivs;
    vector<pair<int, int>> badivs;
    for(int i = 1; i <= n; i++) {
        if(b[i] > (n - 1) / i + 1) {
            cout << 0 << endl;
            return;
        }
        badivs.push_back({b[i] * i, (b[i] + 1) * i - 1});
        for(int j = 0; j < b[i]; j++) {
            goodivs.push_back({j * i, (j + 1) * i - 1});
        }
    }
    vector<int> d(n + 1);
    for(auto [l, r] : badivs) {
        d[min(n, l)]++;
        d[min(n, r + 1)]--;
    }
    int csm = 0;
    vector<int> gnums;
    for(int i = 0; i < n; i++) {
        csm += d[i];
        if(csm == 0) {
            gnums.push_back(i);
        }
    }
    set<pair<int, int>> st;
    sort(goodivs.begin(), goodivs.end(), [&] (pair<int, int> iv, pair<int, int> iv2) {
        return iv.second - iv.first < iv2.second - iv2.first;
    });
    for(auto [l, r] : goodivs) {
        auto it = st.lower_bound({l, 0});
        if(it != st.end() && it->second <= r) {
            continue;
        }
        st.insert({l, r});
    }

    vector<pair<int, int>> impivs(st.begin(), st.end());
    int l = 0, r = 0;
    vector<int> dp(impivs.size() + 1);
    dp[0] = 1;
    int poss = 1;
    for(int i : gnums) {
        while(l < impivs.size() && impivs[l].second < i) {
            poss += MOD - dp[l];
            poss %= MOD;
            l++;
        }
        while(r < impivs.size() && impivs[r].first <= i) r++;
        dp[r] += poss;
        dp[r] %= MOD;
        poss += poss;
        poss %= MOD;
    }
    cout << dp[impivs.size()] << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

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

using ll = long long;

struct BIT {
    vector<ll> tr;
    BIT(int n) : tr(n + 1) {}
    void add(int k, ll x) {
        while(k < tr.size()) {
            tr[k] += x;
            k += k&-k;
        }
    }
    ll sum(int k) {
        ll res = 0;
        while(k > 0) {
            res += tr[k];
            k -= k&-k;
        }
        return res;
    }
};

void tc() {
    int n; cin >> n;
    vector<int> a(n), p(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> p[i]; p[i]--;
    }
    reverse(p.begin(), p.end());
    BIT bit(n);
    set<int> imp; 
    vector<int> ans(n);
    for(int i = 0; i < n; i++) {
        int k = p[i];
        auto it = imp.upper_bound(k);
        int pimp;
        if(it == imp.begin() || bit.sum(k) - bit.sum(*prev(it)) < a[k]) {
            imp.insert(k);
            pimp = k;
        } else {
            pimp = *prev(it);
        }
        bit.add(k + 1, a[k]);
        while(imp.upper_bound(k) != imp.end()) {
            int j = *imp.upper_bound(k);
            if(bit.sum(j) - bit.sum(pimp) >= a[j]) {
                imp.erase(j);
            } else {
                break;
            }
        }
        ans[i] = imp.size() - 1;
    }
    reverse(ans.begin(), ans.end());
    for(int i : ans) cout << i << " ";
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

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

using ll = long long;

const int MOD = 1e9 + 7;

void tc() {
    int n; cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    int k = n / 2;

    int val = 1;
    for(int i = 1; i <= k; i++) {
        val = (ll)i * val % MOD;
    }
    for(int i = 1; i <= k - (n % 2 == 0 ? 2 : 1); i++) {
        val = (ll)i * val % MOD;
    }

    set<ll> xposs;
    xposs.insert(a[n - 1] - a[n - 2]);
    xposs.insert(a[n - 1] - a[n - 3]);

    int ans = 0;
    for(ll x : xposs) {
        vector<ll> b;
        for(int i = 0; i < k; i++) {
            b.push_back(i * x);
        }
        for(int i = 0; i < n - k; i++) {
            b.push_back(a[n - 1] - i * x);
        }
        sort(b.begin(), b.end());
        if(a == b) {
            ans += val;
            if(ans >= MOD) ans -= MOD;
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

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

void tc() {
    int n; cin >> n;

    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) cin >> a[i], a[i]--;
    for(int i = 0; i < n; i++) cin >> b[i], b[i]--;

    int badcnt = 0;
    for(int i = 0; i < n; i++) {
        badcnt += a[i] != b[i];
    }
    if(badcnt == 0) {
        cout << "0 1\n";
        return;
    }

    // mark everything which will ever be reached
    vector<bool> useful(n);
    for(int i = 0; i < n; i++) {
        if(a[i] == b[i]) continue;
        int x = i;
        while(!useful[x]) {
            useful[x] = true;
            x = b[x];
        }
    }

    // anything with b[i] == i once we reach we can't reach anything else, 
    // at most one of them can exit
    vector<int> ends;
    for(int i = 0; i < n; i++) {
        if(useful[i] && b[i] == i) ends.push_back(i);
    }

    if(ends.size() > 1) {
        cout << "-1\n";
        return;
    }

    vector<vector<int>> adj(n), radj(n);
    for(int i = 0; i < n; i++) {
        if(a[i] > b[i]) {
            cout << "-1\n";
            return;
        }
        for(int j = a[i]; j <= b[i]; j++) {
            adj[i].push_back(j);
            radj[j].push_back(i);
        }
    }

    // tarjan algorithm, from cp-algorithms
    vector<int> st;    // - stack holding the unclaimed vertices
    vector<int> roots(n, -1); // - keeps track of the SCC roots of the vertices
    int timer = 0;         // - dfs timestamp counter
    vector<int> t_in(n, -1);  // - keeps track of the dfs timestamp of the vertices
    vector<int> t_low(n, -1); // - keeps track of the lowest t_in of unclaimed vertices
    // reachable in the subtree

    // implements the tarjan algorithm for strongly connected components
    auto dfs = [&](auto&& self, int s) -> void {
        t_low[s] = t_in[s] = timer++;
        st.push_back(s);

        for (auto u : adj[s]) {
            if (t_in[u] == -1) { // tree-edge
                self(self, u);
                t_low[s] = min(t_low[s], t_low[u]);
            } else if (roots[u] == -1) { // back-edge, cross-edge or forward-edge to an unclaimed vertex
                t_low[s] = min(t_low[s], t_in[u]);
            }
        }

        if (t_low[s] == t_in[s]) { // vertex is a root
            while (true) {
                int u = st.back();
                st.pop_back();
                roots[u] = s; // claims the vertex
                if (u == s)
                    break;
            }
        }
    };

    // applies the tarjan algorithm to all the vertices
    for (int v = 0; v < n; v++) {
        if (t_in[v] == -1) {
            dfs(dfs, v);
        }
    }
    vector<vector<int>> comps(n);
    for(int v = 0; v < n; v++) {
        comps[roots[v]].push_back(v);
    }

    vector<int> p(n, -1);
    vector<int> sz(n);
    for(int i = 0; i < n; i++) {
        if(a[i] != b[i]) {
            sz[roots[i]]++;
        }
        if(useful[i] && roots[i] != roots[b[i]]) {
            if(p[roots[b[i]]] != -1) {
                cout << "-1\n";
                return;
            }
            p[roots[b[i]]] = roots[i];
        }
    }
    vector<int> chain;
    int x = roots[ends[0]];
    int csz = 0;
    while(x != -1) {
        chain.push_back(x);
        csz += sz[x];
        x = p[x];
    }
    if(csz != badcnt) {
        cout << "-1\n";
        return;
    }
    reverse(chain.begin(), chain.end());

    {
        x = comps[chain[0]][0];
        vector<int> ops;
        auto op1 = [&] () {
            ops.push_back(1);
            a[x]++;
        };
        auto op2 = [&] () {
            ops.push_back(2);
            x = a[x];
        };
        auto solve_scc = [&] () {
            int rt = roots[x];
            vector<int> comp = comps[rt];

            vector<int> p2(n, -1);
            // only one thing in comp case
            auto rdfs = [&] (auto&& self, int s) -> void {
                for(int u : radj[s]) {
                    if(roots[u] != rt) continue;
                    if(p2[u] == -1) {
                        p2[u] = s;
                        self(self, u);
                    }
                }
            };

            // root a tree
            rdfs(rdfs, comp[0]);

            for(int i = 0; i < comp.size(); i++) {
                while(x != comp[i]) {
                    while(a[x] < max(p2[x], comp[i])) op1();
                    op2();
                }
                while(a[x] < b[x]) op1();
                op2();
            }
        };
        for(int i = 0; i < chain.size(); i++) solve_scc();

        cout << ops.size() << " " << comps[chain[0]][0] + 1 << endl;
        for(int i : ops) cout << i << " ";
        cout << endl;

        for(int i = 0; i < n; i++) assert(a[i] == b[i]);
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

With this, you can prove a significantly simpler solution. We will add this proof later.

// Note: AI generated solution
#include <bits/stdc++.h>
using namespace std;

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

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n + 1), b(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i <= n; i++) {
            cin >> b[i];
        }

        int start = 1, remaining = 0;
        bool possible = true;

        for (int i = 1; i <= n; i++) {
            if (a[i] > b[i]) {
                possible = false;
            }
            if (a[i] < b[i]) {
                if (remaining == 0) {
                    start = i;
                }
                remaining++;
            }
        }

        if (!possible) {
            cout << -1 << '\n';
            continue;
        }

        vector<int> operations;
        int position = start;

        while (remaining > 0) {
            if (a[position] < b[position]) {
                while (a[position] < b[position] &&
                       (a[position] >= position ||
                        a[a[position]] == b[a[position]])) {
                    a[position]++;
                    operations.push_back(1);
                }

                if (a[position] == b[position]) {
                    remaining--;
                }
            }

            if (remaining == 0 || a[position] == position) {
                break;
            }

            operations.push_back(2);
            position = a[position];
        }

        if (remaining > 0) {
            cout << -1 << '\n';
            continue;
        }

        cout << operations.size() << ' ' << start << '\n';
        for (int operation : operations) {
            cout << operation << ' ';
        }
        cout << '\n';
    }
}

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

int MOD;

void madd(int& a, int b) {
    a += b;
    if(a >= MOD) a -= MOD;
}

void msub(int& a, int b) {
    a -= b;
    if(a < 0) a += MOD;
}

int mmul(int a, int b) {
    return 1LL * a * b % MOD;
}

int bpow(int x, int y) {
    return y == 0 ? 1 : mmul((y % 2) ? x : 1, bpow(mmul(x, x), y / 2));
}

void tc() {
    int n; cin >> n >> MOD;
    vector<int> f(2 * n + 1), invf(2 * n + 1);
    f[0] = 1;
    for(int i = 1; i <= 2 * n; i++) {
        f[i] = mmul(f[i - 1], i);
    }
    invf[2 * n] = bpow(f[2 * n], MOD - 2);
    for(int i = 2 * n; i >= 1; i--) {
        invf[i - 1] = mmul(invf[i], i);
    }
    auto F = [&] (int n, int k) -> int {
        return mmul(f[n], mmul(invf[k + 1], invf[n - k]));
    };
    auto choose = [&] (int n, int k) -> int {
        return mmul(f[n], mmul(invf[k], invf[n - k]));
    };
    vector<vector<int>> p(n + 1, vector<int>(n + 1));
    for(int i = 0; i <= n; i++) {
        p[0][i] = mmul(F(2 * i, i), F(2 * i, i));
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= n; j++) {
            for(int k = 0; j + k <= n; k++) {
                madd(p[i][j + k], mmul(p[i - 1][j], p[0][k]));
            }
        }
    }
    vector<int> ans(n + 1);
    for(int i = 0; i <= n; i++) {
        ans[i] = mmul(F(2 * n, i), p[i][n - i]);
    }
    for(int i = n - 1; i >= 0; i--) {
        for(int j = i + 1; j <= n; j++) {
            msub(ans[i], mmul(ans[j], choose(j, i)));
        }
    }
    for(int i = 0; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t; 
    while(t--) tc();
}

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

const int MXN = 400;

template<size_t SZ> int compute_inv(const vector<bitset<SZ>>& mat, vector<bitset<SZ>>& inv) {
    int n = mat.size();
    vector<bool> empty(n, true);
    vector<bitset<SZ>> basis(n);

    for(int i = 0; i < n; i++) {
        bitset<SZ> cur = mat[i];
        bitset<SZ> curinv;
        curinv[i] = 1;
        for(int j = 0; j < n; j++) {
            if(cur[j]) {
                if(empty[j]) {
                    basis[j] = cur;
                    inv[j] = curinv;
                    empty[j] = false;
                    break;
                } else {
                    cur ^= basis[j];
                    curinv ^= inv[j];
                }
            }
        }
    }
    for(int i = 0; i < n; i++) {
        if(empty[i]) return 0;
    }

    for(int i = n - 1; i >= 1; i--) {
        for(int j = 0; j < i; j++) {
            if(basis[j][i]) {
                basis[j] ^= basis[i];
                inv[j] ^= inv[i];
            }
        }
    }
    return 1;
}

bool try_removal(vector<pair<int, int>> cells, vector<bitset<MXN>>& mat, vector<bitset<MXN>>& inv, vector<int>& row_cnt) {
    int n = mat.size(), k = cells.size();
    for(auto [x, y] : cells) {
        if(mat[x][y] == 0) {
            return false;
        }
    }
    assert(k < 4);
    vector<bitset<3>> K(k); 
    for(int i = 0; i < k; i++) {
        for(int j = 0; j < k; j++) {
            K[i][j] = (i == j) ^ inv[cells[i].second][cells[j].first];
        }
    }
    vector<bitset<3>> invK(cells.size());
    if(!compute_inv(K, invK)) {
        return false;
    }
    for(auto [x, y] : cells) {
        mat[x][y] = 0;
        row_cnt[x]--;
    }

    auto old = inv;
    for(int i = 0; i < n; i++) {
        bitset<3> coef;
        for(int alpha = 0; alpha < k; alpha++) {
            int r = cells[alpha].first;

            if(old[i][r]) {
                coef ^= invK[alpha];
            }
        }

        // delta = coef * (V^T * old)
        for(int beta = 0; beta < k; beta++) {
            if(coef[beta]) {
                int c = cells[beta].second;
                inv[i] ^= old[c];
            }
        }
    }
    return true;
}

vector<int> compute_matching(const vector<bitset<MXN>>& mat) {
    int n = mat.size();
    vector<vector<int>> adj(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(mat[i][j]) adj[i].push_back(j);
        }
    }

    vector<int> match(n, -1);
    vector<bool> done(n);

    function<bool(int)> dfs = [&] (int s) {
        for(int u : adj[s]) {
            if(!done[u]) {
                done[u] = true;

                if(match[u] == -1 || dfs(match[u])) {
                    match[u] = s;
                    return true;
                }
            }
        }
        return false;
    };

    for(int i = 0; i < n; i++) {
        fill(done.begin(), done.end(), false);
        dfs(i);
    }

    for(int i = 0; i < n; i++) {
        assert(match[i] != -1);
    }
    return match;
}

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

    vector<bitset<MXN>> mat(n);
    vector<int> row_cnt(n);
    for(int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        x--, y--;
        mat[x][y] = 1;
        row_cnt[x]++;
    }

    vector<bitset<MXN>> inv(n);
    compute_inv(mat, inv);

    int sm = m;
    int left = (sm + n - 1) / n;
    cout << left << '\n';

    while(sm > 0) {
        vector<bitset<MXN>> omat = mat;
        if(sm <= n) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    mat[i][j] = 0;
                }
            }
            row_cnt.assign(n, 0);
        } else if(sm <= 2 * n) {
            vector<int> matching = compute_matching(mat);
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    mat[i][j] = 0;
                }
            }
            row_cnt.assign(n, 0);
            for(int i = 0; i < sm - n; i++) {
                mat[matching[i]][i] = 1;
                row_cnt[matching[i]]++;
            }
        } else if(sm <= 3 * n) {
            vector<int> matching = compute_matching(mat);
            int above = 0;
            for(int i = 0; i < n; i++) {
                for(int j = matching[i] + 1; j < n; j++) {
                    above += mat[j][i];
                }
            }

            vector<bitset<MXN>> nmat(n);
            vector<int> nrow_cnt(n);
            int ones_left = sm - n;
            for(int i = 0; i < n; i++) {
                nmat[matching[i]][i] = 1;
                nrow_cnt[matching[i]]++;
                ones_left--;
            }
            // make matrix either upper or lower triangular, whichever one
            // removes a sufficient number of ones
            if(above >= ones_left) {
                for(int i = 0; i < n; i++) {
                    for(int j = matching[i] + 1; j < n; j++) {
                        if(mat[j][i]) {
                            ones_left--;
                            nmat[j][i] = 1;
                            nrow_cnt[j]++;
                            if(ones_left == 0) break;
                        }
                    }
                    if(ones_left == 0) break;
                }
            } else {
                for(int i = 0; i < n; i++) {
                    for(int j = 0; j < matching[i]; j++) {
                        if(mat[j][i]) {
                            ones_left--;
                            nmat[j][i] = 1;
                            nrow_cnt[j]++;
                            if(ones_left == 0) break;
                        }
                    }
                    if(ones_left == 0) break;
                }
            }
            mat = nmat;
            row_cnt = nrow_cnt;
        } else {
            int csm = sm;
            if(n % 2) {
                // odd case (remove either 1 or 3)
                int dup_row = -1;
                for(int i = 0; i < n; i++) {
                    if(row_cnt[i] >= 2) {
                        dup_row = i;
                        break;
                    }
                }
                assert(dup_row != -1);

                vector<int> cols;
                for(int i = 0; i < n; i++) {
                    if(mat[dup_row][i]) cols.push_back(i);
                }

                assert(cols.size() >= 2);

                for(int i = 0; i < n; i++) {
                    if(try_removal({{i, cols[0]}}, mat, inv, row_cnt)) {
                        csm--;
                        break;
                    }
                    if(try_removal({{i, cols[1]}}, mat, inv, row_cnt)) {
                        csm--;
                        break;
                    }
                }

                if(csm == sm) {
                    for(int i = 0; i < n; i++) {
                        if(i != dup_row) {
                            // remove L shape
                            if(try_removal(
                                    {{i, cols[0]}, 
                                     {dup_row, cols[0]}, 
                                     {dup_row, cols[1]}},
                                mat, inv, row_cnt)) {
                                csm -= 3;
                                break;
                            }
                        }
                    }
                    assert(sm != csm);
                }
            }

            while(csm > sm - n) {
                // remove 2 at a time
                int dup_row = -1;
                for(int i = 0; i < n; i++) {
                    if(row_cnt[i] >= 3) {
                        dup_row = i;
                        break;
                    }
                }

                vector<int> cols;
                for(int i = 0; i < n; i++) {
                    if(mat[dup_row][i]) cols.push_back(i);
                }

                assert(cols.size() >= 3);

                if(!try_removal({{dup_row, cols[0]}, {dup_row, cols[1]}}, mat, inv, row_cnt)) {
                    if(!try_removal({{dup_row, cols[1]}, {dup_row, cols[2]}}, mat, inv, row_cnt)) {
                        if(!try_removal({{dup_row, cols[0]}, {dup_row, cols[2]}}, mat, inv, row_cnt)) {
                            assert(false);
                        }
                    }
                }

                csm -= 2;
            }
            assert(csm == sm - n);
        }

        vector<pair<int, int>> move;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(omat[i][j] == 1 && mat[i][j] == 0) {
                    move.push_back({i, j});
                }
            }
        }
        cout << move.size() << "\n";
        for(auto [x, y] : move) cout << x + 1 << " " << y + 1 << "\n";
        sm -= n;

        int csm = 0;
        for(int i = 0; i < n; i++) {
            csm += row_cnt[i];
        }
        assert(csm == max(0, sm));
    }
}

int main() {
    int t; cin >> t;
    while(t--) tc();
}

Will be added later; credit to BurnedChicken for finding this in testing! This method results in a much simpler solution!

include <bits/stdc++.h>

using namespace std;

const int SZ = 400;

template int compute_inv(const vector<bitset>& mat, vector<bitset>& inv) { int n = mat.size(); vector empty(n, true); vector<bitset> basis(n);

for(int i = 0; i < n; i++) {
    bitset<SZ> cur = mat[i];
    bitset<SZ> curinv;
    curinv[i] = 1;
    for(int j = 0; j < n; j++) {
        if(cur[j]) {
            if(empty[j]) {
                basis[j] = cur;
                inv[j] = curinv;
                empty[j] = false;
                break;
            } else {
                cur ^= basis[j];
                curinv ^= inv[j];
            }
        }
    }
}
for(int i = 0; i < n; i++) {
    if(empty[i]) return 0;
}

for(int i = n - 1; i >= 1; i--) {
    for(int j = 0; j < i; j++) {
        if(basis[j][i]) {
            basis[j] ^= basis[i];
            inv[j] ^= inv[i];
        }
    }
}
return 1;

}

void tc() { int n, m; cin >> n >> m; vector<bitset> mat(n); for(int i = 0; i < m; i++) { int x, y; cin >> x >> y; x--, y--; mat[x][y] = 1; }

vector<bitset<SZ>> inv(n);
compute_inv(mat, inv);
vector<int> cnts(2 * n);
for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        cnts[i] += mat[i][j];
        cnts[n + j] += mat[i][j];
    }
}
queue<pair<int, int>> mustq, freeq;
vector<pair<int, int>> centers;
vector<vector<pair<int, int>>> moves;
while(true) {
    while(mustq.size() + freeq.size() < n) {
        int best_rc = 0;
        for(int rc = 0; rc < 2 * n; rc++) {
            if(cnts[rc] >= cnts[best_rc]) best_rc = rc;
        }
        if(cnts[best_rc] == 0) {
            break;
        }

        int x = -1, y = -1;
        if(best_rc < n) {
            x = best_rc;
            for(int j = 0; j < n; j++) {
                if(mat[x][j] && inv[j][x]) {
                    y = j;
                    break;
                }
            }
        } else {
            y = best_rc - n;
            for(int j = 0; j < n; j++) {
                if(mat[j][y] && inv[y][j]) {
                    x = j;
                    break;
                }
            }
        }
        assert(x != -1 && y != -1);

        centers.push_back({x, y});
        vector<pair<int, int>> must, free;
        auto erase = [&] (int a, int b) {
            mat[a][b] = 0;
            cnts[a]--;
            cnts[b + n]--;
        };
        for(int j = 0; j < n; j++) {
            if(mat[x][j] && j != y) {
                must.push_back({x, j});
                erase(x, j);
            }
        }
        for(int j = 0; j < n; j++) {
            if(mat[j][y] && j != x) {
                free.push_back({j, y});
                erase(j, y);
            }
        }
        erase(x, y);
        assert(cnts[x] == 0 && cnts[n + y] == 0);

        if(best_rc < n) swap(must, free);
        for(auto u : must) mustq.push(u);
        for(auto u : free) freeq.push(u);

        bitset<SZ> row = inv[y];
        for(int j = 0; j < n; j++) {
            if(cnts[j + n] > 0 && inv[j][x]) {
                inv[j] ^= row;
            }
        }
    }
    int left = n;
    vector<pair<int, int>> move;
    while(left > 0 && mustq.size() > 0) {
        left--;
        move.push_back(mustq.front());
        mustq.pop();
    }
    while(left > 0 && freeq.size() > 0) {
        left--;
        move.push_back(freeq.front());
        freeq.pop();
    }
    while(left > 0 && centers.size() > 0) {
        left--;
        move.push_back(centers.back());
        centers.pop_back();
    }
    moves.push_back(move);
    if(centers.size() == 0) break;
}
cout << moves.size() << "\n";
for(auto move : moves) {
    cout << move.size() << "\n";
    for(auto [u, v] : move) cout << u + 1 << " " << v + 1 << "\n";
}

}

int main() { ios::sync_with_stdio(false), cin.tie(nullptr); int t; cin >> t; while(t--) tc(); }