#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
#define FORi(i,a,b) for(int i=a;i<b;i++)
#define FOR(i,n) FORi(i,0,n)
#define FOA(v,n) for(auto v : n)
#define len(a) ((int)a.size())
typedef vector<int> vi;
map<int, vi> points;
bool vis[100000];
vi X,Y,c;
#define neg(v) (-v-1)
#define MOD 10000000
#define MID ((l+r)/2)
void make(int pos, int l, int r){
if(l+1>=r) return;
int a1 = len(X);
int a2 = len(X)+1;
X.push_back(MOD);
X.push_back(MOD);
Y.push_back(MOD);
Y.push_back(MOD);
X[pos] = neg(a1);
Y[pos] = neg(a2);
make(a1, l, MID);
make(a2, MID+1, r);
}
void rec(int cur){
////cout<<"Recursing "<<cur<<endl;
vis[cur] = true;
int req_level = ceil(log2(len(points[cur])));
////cout<<"LEVELS "<<cur<<" "<<len(points[cur])<<endl;
if(cur>0 && len(points[cur]) && req_level){
int org = len(X);
c[cur] = neg(org);
X.push_back(MOD);
Y.push_back(MOD);
//FOR(i,len(X)) cout<<-i-1<<" "<<X[i]<<" "<<Y[i]<<endl;
//cout<<endl;
int min_needed = 1<<req_level;
make(org, 0, min_needed-1);
//FOR(i,len(X)) cout<<-i-1<<" "<<X[i]<<" "<<Y[i]<<endl;
//cout<<endl;
points[cur].insert(points[cur].begin(), min_needed - len(points[cur]), neg(org));
//cout<<"points: ";
//FOA(v,points[cur]) cout<<v<<" ";
//cout<<endl;
FOR(i,min_needed){
int t = i;
int cnt=req_level;
int pos = org;
//cout<<cnt<<endl;
while(cnt>1){
if(t%2) pos = -Y[pos]-1;
else pos = -X[pos]-1;
t/=2;
cnt--;
//cout<<i<< " "<<t<<" "<<pos<<endl;
}
//cout<<i<< " "<<t<<" "<<pos<<endl;
int anss = neg(org);
anss = points[cur][i];
//cout<<anss<<endl;
//assert(min_needed>=len(points[cur]));
////if(min_needed>len(points[cur])+i) anss = points[cur][min_needed-len(points[cur])+i-1],cout<<"yeeting "<<anss<<endl;
//cout<<anss<<endl;
if(t%2) Y[pos] = anss;
else X[pos] = anss;
//FOR(i,len(X)) cout<<-i-1<<" "<<X[i]<<" "<<Y[i]<<endl;
//cout<<endl;
}
//FOR(i,len(X)) cout<<-i-1<<" "<<X[i]<<" "<<Y[i]<<endl;
//cout<<endl;
}
else c[cur] = points[cur][0];
////cout<<"Recursing "<<cur<<endl;
FOA(v,points[cur]) if(!vis[v] && v>=0) rec(v);
}
void create_circuit(int M, std::vector<int> A) {
c.resize(M+1);
A.push_back(0);
int prev=0;
points[0].push_back(A[0]);
FOR(i,len(A)-1){
points[A[i]].push_back(A[i+1]);
}
rec(0);
//cout<<"---\n";
//FOR(i,M+1) cout<<i<<" "<<c[i]<<endl;
////FOR(i,len(X)) cout<<-i-1<<" "<<X[i]<<" "<<Y[i]<<endl;
answer(c, X, Y);
}
