//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "chameleon.h"
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
namespace {
vector<int> ord, adj[maxn];
bool vis[maxn];
bool bad[maxn][maxn];
void dfs(int n, int c, vector<int> &lef, vector<int> &rig) {
vis[n] = 1;
if (c) rig.push_back(n);
else lef.push_back(n);
for (int v:adj[n]) {
if (!vis[v]) dfs(v, 1 - c, lef, rig);
}
}
int query(int x, vector<int> &v, int l, int r) { //[l, r)
//debug(x, l, r);
vector<int> vec;
vec.push_back(ord[x]);
for (int i = l;i < r;i++) vec.push_back(ord[v[i]]);
if (r - l == 0) return 1;
else return r - l + 1 - Query(vec);
}
void addedge(int x, vector<int> &v, int l) {
if (l >= v.size() || !query(x, v, l, v.size())) return;
int low = l, up = v.size();
while (low < up - 1) {
int mid = (low + up) / 2;
if (query(x, v, low, mid)) up = mid;
else low = mid;
}
adj[x].push_back(v[low]);
adj[v[low]].push_back(x);
debug("edge", x, v[low]);
addedge(x, v, low + 1);
}
}
void Solve(int N) {
srand(time(NULL));
vector<int> lef, rig;
for (int i = 1;i <= 2 * N;i++) ord.push_back(i);
//random_shuffle(ord.begin(), ord.end());
ord.insert(ord.begin(), 0);
//pary(ord.begin(), ord.end());
for (int i = 2 * N;i > 0;i--) {
random_shuffle(lef.begin(), lef.end());
random_shuffle(rig.begin(), rig.end());
addedge(i, lef, 0);
addedge(i, rig, 0);
for (int j = i;j <= 2 * N;j++) vis[j] = 0;
lef.clear(), rig.clear();
for (int j = i;j <= 2 * N;j++) {
if (!vis[j]) dfs(j, rand() % 2, lef, rig);
}
pary(lef.begin(), lef.end());
pary(rig.begin(), rig.end());
debug();
}
debug();
auto getbad = [&](vector<int> &vec) {
for (int i:vec) {
if (adj[i].size() == 3) {
vector<int> t1(1, ord[i]), t2(1, ord[i]);
t1.push_back(ord[adj[i][0]]);
t1.push_back(ord[adj[i][2]]);
t2.push_back(ord[adj[i][0]]);
t2.push_back(ord[adj[i][1]]);
pary(t1.begin(), t1.end());
pary(t2.begin(), t2.end());
int val = 0;
if (Query(t1) == 1) val = 1;
else if (Query(t2) == 1) val = 2;
bad[i][adj[i][val]] = bad[adj[i][val]][i] = 1;
}
}
};
getbad(lef), getbad(rig);
for (int i:lef) {
debug(i);
if (adj[i].size() == 1) debug(ord[i], ord[adj[i][0]]), Answer(ord[i], ord[adj[i][0]]);
else {
for (int v:adj[i]) {
if (!bad[i][v]) debug(ord[i], ord[adj[i][0]]), Answer(ord[i], ord[v]);
}
}
}
}
