#include "doll.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
vector<int>to[200015],g[200015];
vector<int>ans1,ans2,c;
int n,m,now=0,vis[400015];
pii seg[400015];
int build(int num,int l,int r,int root,int out){
if (l==r){
if (out) return root;
return -root;
}
int mid=(l+r)>>1,use=--now;
use=abs(use);
if (out<(mid-l+1)){
seg[use].x=build(num,l,mid,root,out);
seg[use].y=build(num,mid+1,r,root,0);
}
else {
out-=(mid-l+1);
seg[use].x=root;
seg[use].y=build(num,mid+1,r,root,out);
}
return use;
}
void dfs(int num,int i,int order,int root){
if (order==g[num].size()) return;
if (!vis[i]){
vis[i]^=1;
if (seg[i].x==-root)
ans1[i]=g[num][order++];
else ans1[i]=-seg[i].x;
dfs(num,abs(seg[i].x),order,root);
}
else {
vis[i]^=1;
if (seg[i].y==-root)
ans2[i]=g[num][order++];
else ans2[i]=-seg[i].y;
dfs(num,abs(seg[i].y),order,root);
}
return;
}
void create_circuit(int M, std::vector<int> A) {
m=M;
ans1.resize(400000); ans2.resize(400000);
A.push_back(0);
n = A.size();
for (int i=0;i<n-1;i++){
g[A[i]].push_back(A[i+1]);
}
c.resize(m+1);
int now_root=0;
for (int i=0;i<=m;i++){
if (g[i].empty()) c[i]=0;
else if (g[i].size()==1) c[i]=g[i][0];
else {
int p=__lg((int)(g[i].size()-1))+1;
now_root=abs(now)+1;
c[i]=-now_root;
build(i,0,(1LL<<p)-1,now_root,(1LL<<p)-g[i].size());
dfs(i,now_root,0,now_root);
}
}
c[0]=A[0];
now=abs(now);
vector<int>X,Y;
for (int i=1;i<=now;i++){
X.push_back(ans1[i]);
}
for (int i=1;i<=now;i++){
Y.push_back(ans2[i]);
}
answer(c, X, Y);
}
/*
2 16
1 2 2 1 2 2 1 1 1 1 2 2 2 1 2 2 2 1 1 2 2 2 1
4 5
1 2 1 3 1
./rand
./doll
*/
