#include <bits/stdc++.h>
#include "doll.h"
#define ll long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pll pair<ll,ll>
using namespace std;
ll n, m, s, nxt[100005], k=0;
pll a[400005];
vector<ll> v[100005];
bool tt[400005];
ll build(int l,int r)
{
if (l==r)
{
return 0;
}
s--;
int w=(l+r)/2;
a[-s].fi=build(l,w);
a[-s].se=build(w+1,r);
return s;
}
ll dfs(int nw,int l,int r,int k)
{
if (l==r)
{
return k;
}
int w=(l+r)/2;
if (!tt[nw])
{
ll o=dfs(a[-nw].fi, l, w, k);
if (o!=-1) a[-nw].fi=o;
}else
{
ll o=dfs(a[-nw].se, w+1, r, k);
if (o!=-1) a[-nw].se=o;
}
tt[nw]^=1;
return -1;
}
void create_circuit(int m, vector<int> aa) {
s=0;
aa.pb(0);
for (int i = 0; i < aa.size()-1; i++)
{
v[aa[i]].pb(aa[i+1]);
}
nxt[0]=aa[0];
for (int i = 1; i <= m; i++)
if (v[i].size()>0)
{
if (v[i].size()==1)
nxt[i]=v[i][0]; else
{
ll o=build(0,v[i].size()-1);
nxt[i]=o;
for (int j = 0; j < v[i].size(); j++)
dfs(o, 0, v[i].size()-1, v[i][j]);
}
}
std::vector<int> X, Y, C;
X.resize(-s);
Y.resize(-s);
C.resize(m+1);
for (int i = 0; i <= m; i++)
C[i]=(int)nxt[i];
for (int i = -1; i >= s; i--)
X[-i-1]=(int)a[-i].fi, Y[-i-1]=(int)a[-i].se;
/*for (int i = 0; i < C.size(); i++)
cout << C[i] << " ";
cout << "\n";
for (int i = 0; i < X.size(); i++)
cout << X[i] << " ";
cout << "\n";
for (int i = 0; i < Y.size(); i++)
cout << Y[i] << " ";
cout << "\n";*/
answer(C, X, Y);
}
