#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); } vector<int> get_vec(set<int> s, int a, int b) { int idx = 0; vector<int> ans; for(auto x : s) { if(a<=idx && idx <= b)ans.push_back(x); idx++; } return ans; } void Solve(int N) { vector<set<int>> V(2*N+1); vector<vector<int>> G(2*N+1); vector<set<int>> sets(2); vector<int> is_sure(2*N+1); for(int i=1; i<=2*N; ++i) { int put = -1; for(int k=0; k<3; ++k) { vector<int> q = get_vec(sets[k], 0, sets[k].size()-1); 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 = get_vec(sets[k], start, mid); p.push_back(i); if(p.size() - Query(p) > 0) hi = mid; else lo = mid+1; } vector<int> doc = get_vec(sets[k], lo, lo); G[i].push_back(doc[0]); G[doc[0]].push_back(i); start = lo+1; q = get_vec(sets[k], start, sets[k].size()-1); q.push_back(i); Q = Query(q); } } if(i<=N) put = 0; else put=1; sets[put].insert(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(); }