#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; #include "chameleon.h" template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; set<pair<int, int>> Sa; void Ans(int x, int y) { if(x>y) swap(x,y); if(x==y) return; Sa.insert({x,y}); } void Finish() { for(auto[a,b] : Sa) Answer(a,b); } void Solve(int N) { vector<set<int>> V(2*N+1); vector<vector<int>> G(2*N+1); vector<vector<int>> sets(4); for(int i=1; i<=2*N; ++i) { int put = 0; for(int k=0; k<2; ++k) { vector<int> q = sets[k]; q.push_back(i); int Q = Query(q); if(q.size()==Q) put = k; int start = 0; while(q.size() - Q > 0) { int lo = 0; int hi = sets[k].size() - 1; while(lo < hi) { int mid=(lo+hi)/2; vector<int> p; p.push_back(i); for(int j=start; j<=mid; ++j) p.push_back(sets[k][j]); if(p.size() - Query(p) > 0) hi = mid; else lo = mid+1; } G[i].push_back(sets[k][lo]); G[sets[k][lo]].push_back(i); start = lo+1; while(q.size()) q.pop_back(); for(int j=start; j<sets[k].size(); ++j) q.push_back(sets[k][j]); q.push_back(i); Q = Query(q); } } if(i<=N) put = 0; else put=1; sets[put].push_back(i); } for(int i=1; i<=2*N; ++i) for(auto x : G[i]) V[i].insert(x); for(int i=1; i<=2*N; ++i) { if(V[i].size()==1) Ans(i,*V[i].begin()); else { vector<int> v; for(auto x : G[i]) v.push_back(x); for(int j=0; j<3; ++j) { vector<int> p = {i}; for(int x=0; x<3; ++x) if(x!=j) p.push_back(v[x]); if(Query(p)==1) { V[i].erase(v[j]); V[v[j]].erase(i); } } } } for(int i=1; i<=2*N; ++i) { if(V[i].size()==1) Ans(i,*V[i].begin()); } Finish(); }