#include "explore.h"
#include <bits/stdc++.h>
using namespace std; 
const int N = 2e5 + 5; 

mt19937 Rand(time(0)); 
int id[N], die[N], t, a[N], m, T1[N], T2[N], Q[N], idx[N], st[N]; 
vector<int> G[N]; 
vector<int> cklis; 

inline int Query(int x) {
    int u = query(x - 1); 
    for (int i : G[x]) u ^= st[i]; 
    return u; 
}
void solve(int l, int r, int ql, int qr) { // 求解 [ql, qr] 的点连向哪些边：[l, r]
    if (ql > qr) return; 
    // cerr << l << " " << r << " " << ql << " " << qr << " ET::TGERTY\n"; 
    // for (int i = l; i <= r; ++i)
        // cerr << a[i] << " \n"[i == r]; 
    // for (int i = ql; i <= qr; ++i)
        // cerr << Q[i] << " \n"[i == qr]; 
    if (l == r) {
        for (int i = ql; i <= qr; ++i) if (a[l] != Q[i]) {
            // if (st.find({a[l], Q[i]}) == st.end()) 
            report(a[l] - 1, Q[i] - 1); cklis.push_back(a[l]); cklis.push_back(Q[i]); 
            // cerr << a[l] << " " << Q[i] << " FOUND\n"; 
            G[a[l]].emplace_back(Q[i]); 
            G[Q[i]].emplace_back(a[l]); 
            --m; 
        }
        return; 
    }
    int mid = l + r >> 1; 
    for (int i = l; i <= mid; ++i) modify(a[i] - 1), st[a[i]] = 1; 
    int p = 0, q = 0; 
    for (int i = ql; i <= qr; ++i) {
        // int u = Query(Q[i]); 
        if (idx[Q[i]] <= mid || Query(Q[i])) T1[++p] = Q[i]; 
        else T2[++q] = Q[i]; 
    }
    int ba = ql - 1; 
    for (int i = 1; i <= p; ++i) Q[++ba] = T1[i]; 
    for (int i = 1; i <= q; ++i) Q[++ba] = T2[i]; 
    for (int i = l; i <= mid; ++i) modify(a[i] - 1), st[a[i]] = 0; 
    solve(l, mid, ql, ql + p - 1); 
    solve(mid + 1, r, ql + p, qr); 
}

void explore(int n, int M) {
    if (M == 10 * n) {
        for (int i = 0; i < n - 1; ++i) {
            modify(i); st[i] ^= 1; 
            for (int j = i + 1; j < n; ++j)
                if (query(j) != st[j]) st[j] ^= 1, report(i, j); 
        }
        return; 
    }
    // cerr << n << " " << M << "\n"; 
    for (int i = 1; i <= n; ++i) id[i] = i; 
    m = M; 
    while (m) {
        // cerr << m << endl; 
        
        t = 0; 
        for (int i = 1; i <= n; ++i)
            if (!die[id[i]]) a[++t] = id[i], Q[t] = a[t], idx[a[t]] = t; 
        
        int be = m; 
        solve(1, t, 1, t); 
        
        if (m != 0) {
            for (int x : cklis)
                if (check(x - 1)) die[x] = 1; 
            cklis.clear(); 
        }

        shuffle(id + 1, id + n + 1, Rand); 
        // cerr << "--------------------\n"; 
    }
}