#include "doll.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define vb vector<bool>
#define pb push_back
#define vvi vector<vector<int>>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
using namespace std;
void create_circuit(int M, std::vector<int> A) {
vi v;
v.pb(0);
for(auto u : A)v.pb(u);
v.pb(0);
vvi nxt(M+1);
f0r(i, v.size() - 1){
nxt[v[i]].pb(v[i+1]);
}
int curnum = 0;
vi c(M+1);
vi x;
vi y;
f0r(t, M+1){
if(nxt[t].size() >= 2){
int mx = ceil(log2(nxt[t].size()));
int bts = (1 << mx) - nxt[t].size();
int num = -1;
int ptr = 0;
c[t] = curnum - 1;
f0r(i, mx){
f0r(j, (1 << i)){
if(i != mx - 1){
x.pb(curnum + num * 2);
y.pb(curnum + num * 2 - 1);
}
else{
int ind1;
int nind = j*2;
ind1 = 0;
for(int k = mx-1; k>=0; k--){
ind1 += (1 << (mx -1- k)) * (((1 << k) & nind) > 0);
}
//cout<<nind<<' '<<ind1<<'\n';
int nind2 = j*2 + 1;
int ind2 = 0;
for(int k = mx; k>=0; k--){
ind2 += (1 << (mx -1- k)) * (((1 << k) & nind2) > 0);
}
//cout<<nind2<<' '<<ind2<<'\n';
if(ind1 >= bts){
x.pb(nxt[t][ind1 - bts]);
}
else{
x.pb(curnum - 1);
}
if(ind2 >= bts){
y.pb(nxt[t][ind2 - bts]);
}
else{
y.pb(curnum - 1);
}
}
num--;
}
}
curnum += num + 1;
}
else if(nxt[t].size() == 1){
c[t] = nxt[t][0];
}
}
// vout(c);
// vout(x);
// vout(y);
map<int,vi>fr;
f0r(i,c.size()){
fr[c[i]].pb(i);
}
f0r(i, x.size()){
fr[x[i]].pb(i);
}
map<int,int> ne;
map<int,int> nx;
vb tk(x.size());
for(int i = x.size(); i>=0; i--){
if(x[i] == 0 && y[i] == 0){
tk[i] = 1;
nx[i] = x[i];
}
}
int cnt = 0;
f0r(i,x.size()){
if(!tk[i]){
ne[i] = cnt;
cnt++;
}
}
f0r(i, c.size()){
if(c[i] < 0){
if(tk[-c[i] - 1]){
c[i] = nx[-c[i] - 1];
}
else{
c[i] = -ne[-c[i] - 1] - 1;
}
}
}
vi xx; vi yy;
f0r(i, x.size()){
pair<int,int> p;
if(!tk[i]){
if(x[i] < 0){
if(tk[-x[i] - 1]){
p.first = nx[-x[i] - 1];
}
else{
p.first = -ne[-x[i] - 1] - 1;
}
}
else p.first = x[i];
if(y[i] < 0){
if(tk[-y[i] - 1]){
p.second = nx[-y[i] - 1];
}
else{
p.second = -ne[-y[i] - 1] - 1;
}
}
else p.second = y[i];
}
xx.pb(p.first);
yy.pb(p.second);
}
// vout(c);
// vout(xx);
// vout(yy);
answer(c,xx,yy);
}
