# 【題解】Codeforces 1631C. Johnny and Megan’s Necklace

```#include <iostream>
#include <vector>
using namespace std;

int n, a[500005], b[500005], vis[1000005];
vector <pair<int, pair<int, int> > > v[1048576];
vector <int> ans;

void dfs(int x){
while (v[x].size()){
auto i = v[x].back();
v[x].pop_back();
if (vis[i.second.first]) continue;
else {
vis[i.second.first] = 1;
vis[i.second.second] = 1;
dfs(i.first);
ans.push_back(i.second.second);
ans.push_back(i.second.first);
}
}
}

bool solve(int x){
for (int i = 1; i <= n*2; i++){
vis[i] = 0;
}
ans.clear();
for (int i = 0; i < (1<<x); i++){
v[i].clear();
}
for (int i = 0; i < n; i++){
int y = (a[i]&((1<<x)-1)), z = (b[i]&((1<<x)-1));
v[y].push_back({z, {i*2+1, i*2+2}});
v[z].push_back({y, {i*2+2, i*2+1}});
}
for (int i = 0; i < (1<<x); i++){
if (v[i].size() % 2 == 1) return false;
}
for (int i = 0; i < (1<<x); i++){
if (v[i].size()){
dfs(i);
break;
}
}
if (ans.size() == n*2) return true;
else return false;
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i] >> b[i];
}
for (int i = 20; i >= 0; i--){
if (solve(i)){
cout << i << "\n";
break;
}
}
for (int i:ans){
cout << i << " ";
}
}
```