#include "minerals.h" #include<bits/stdc++.h> using namespace std; template<class T>bool minimize(T& a, T b){ if(a > b){ a = b; return true; } return false; } int half_n, n; namespace sub1{ void solve(){ vector<bool>vis(n + 1, false); for(int i = 1; i <= n; i++){ if(!vis[i]){ Query(i); for(int j = i + 1; j <= n; Query(j++)){ if(Query(j) == 1){ Answer(i, j); vis[i] = vis[j] = true; Query(j); break; } } Query(i); } } } } namespace sub23{ void solve(){ vector<int>a, b, low(half_n, 0), high(half_n), ans(half_n); for(int i = 1, pre = 0; i <= n; i++){ if(Query(i) == pre + 1){ pre++; a.push_back(i); } else{ high[b.size()] = int(a.size()) - 1; b.push_back(i); Query(i); } } for(bool start_0 = false; true; start_0 ^= 1){ bool have = false; vector<vector<int>>query(half_n); for(int i = 0; i < half_n; i++){ if(low[i] <= high[i]){ query[(low[i] + high[i]) >> 1].push_back(i); have = true; } } if(!have){ break; } if(start_0){ for(int i = 0; i < half_n; i++){ Query(a[i]); for(int& j : query[i]){ if(Query(b[j]) == i + 1){ high[j] = (ans[j] = i) - 1; } else{ low[j] = i + 1; } Query(b[j]); } } } else{ for(int i = half_n - 1; i > -1; Query(a[i--])){ for(int& j : query[i]){ if(Query(b[j]) == i + 1){ high[j] = (ans[j] = i) - 1; } else{ low[j] = i + 1; } Query(b[j]); } } } } for(int i = 0; i < half_n; i++){ Answer(b[i], a[ans[i]]); } } } const int lim = 43005; const int INF = 1e9; bitset<lim << 1>vis; int cur = 0; void toggle(int x){ vis[x] = !vis[x]; cur = Query(x); } namespace sub45{ void solve(){ vis.reset(); vector<int>a, b; for(int i = 1; i <= n; i++){ toggle(i); if(cur == a.size() + 1){ a.push_back(i); } else{ b.push_back(i); } } int LG = 0; while((1 << LG) < half_n){ LG++; } vector<vector<int>>dp(LG, vector<int>(2, INF)), trace(LG, vector<int>(2, -1)); for(int i = dp[0][0] = dp[0][1] = 0; i < half_n; i++){ dp[0][(i & 1) ^ 1]++; } for(int bit = 1; bit < LG; bit++){ for(int p = 0; p < 2; p++){ for(int c = 0; c < 2; c++){ int val = dp[bit - 1][p]; for(int i = 0; i < half_n; i++){ if(((i >> bit & 1) == c && (i >> (bit - 1) & 1) != p) || ((i >> bit & 1) != c && (i >> (bit - 1) & 1) == p)){ val++; } } if(minimize(dp[bit][c], val)){ trace[bit][c] = p; } } } } vector<bool>z(LG); for(int i = LG - 1, s = dp[i][1] < dp[i][0]; i > -1; s = trace[i--][s]){ z[i] = s; } vector<int>ans(half_n, 0); for(int bit = 0; bit < LG; bit++){ for(int i = 0; i < half_n; i++){ if((vis[a[i]] && (i >> bit & 1) != z[bit]) || (!vis[a[i]] && (i >> bit & 1) == z[bit])){ toggle(a[i]); } } for(int i = 0; i < half_n; i++){ if((ans[i] | (1 << bit)) >= half_n){ continue; } int pre = cur; toggle(b[i]); if((z[bit] && cur == pre) || (!z[bit] && cur != pre)){ ans[i] |= 1 << bit; } } } for(int i = 0; i < half_n; i++){ Answer(b[i], a[ans[i]]); } } } namespace sub6789{ void play(vector<int>a, vector<int>b){ if(a.size() == 1){ Answer(a[0], b[0]); return; } int m = max(1, int(a.size() * 0.38)); for(int i = 0; i < m; i++){ toggle(a[i]); } vector<int>b1, b2; for(int& i : b){ if(b1.size() == m){ b2.push_back(i); } else if(b2.size() == int(a.size()) - m){ b1.push_back(i); } else{ int pre = cur; toggle(i); if(cur == pre){ if(vis[a[0]]){ b1.push_back(i); } else{ b2.push_back(i); } } else if(vis[a[0]]){ b2.push_back(i); } else{ b1.push_back(i); } } } play(vector<int>(a.begin(), a.begin() + m), b1); play(vector<int>(a.begin() + m, a.end()), b2); } void solve(){ vis.reset(); vector<int>a, b; for(int i = 1; i <= n; i++){ toggle(i); if(cur == a.size() + 1){ a.push_back(i); } else{ b.push_back(i); } } play(a, b); } } void Solve(int _n){ n = (half_n = _n) << 1; if(half_n <= 100){ sub1::solve(); } else if(half_n <= 15000){ sub23::solve(); } else if(half_n <= 39000){ sub45::solve(); } else{ sub6789::solve(); } }