#include "doll.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
const int NN=2e5+5;
vector<int> g[NN];
vector<int> x,y;
#define pb push_back
int generate(vector<int> &v, int &s, vector<int> &x, vector<int> &y){
int sz=v.size();
int k=1,K=0;
while(k<sz) k*=2,K++;
vector<int> rev(k);
for(int i=0;i<k;i++)
rev[i]=rev[i/2]/2 | ((i&1) << (K-1));
const int id=--s;
for(int i=0;i<(k-1)/2;i++){
x.pb(--s);
y.pb(--s);
}
for(int i=0;i<k;i++){
vector<int>& u=i%2? y:x;
if(rev[i]<k-sz)
u.pb(id);
else
u.pb(v[rev[i]-(k-sz)]);
}
return id;
}
void create_circuit(int m, vector<int> a) {
int n=a.size();
vector<int> c(m+1);
c[0]=a[0];
for(int i=0;i<n-1;i++){
g[a[i]].push_back(a[i+1]);
c[a[i]]=a[i+1];
}
g[a[n-1]].pb(0);
int id=0;
for(int i=1;i<=m;i++){
int sz=g[i].size();
if(sz<=1) continue;
c[i]=generate(g[i],id,x,y);
}
answer(c,x,y);
}
