#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define vll vector<int>
#define ll int
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
vector<int> XP,YP;
const int NM=1e6+10;
ll cp[NM],label=0,father_of_all=-1;
vll fast_order(ll n)
{
if(n==2)
return {1,2};
vll ans;
ll hn=n/2;
for(int i=1;i<=n;i+=2)
ans.pb(i);
vll hans(hn);
vll np=fast_order(n/2);
for(int j=0;j<hn;j++)
hans[np[j]-1]=ans[j];
ans.clear();
for(auto i:hans)
ans.pb(i);
for(auto i:hans)
ans.pb(i+1);
return ans;
}
vll childx,childy,order_,npp;
int label_it(vll&p,int l,int r,bool lp=0)
{
if((l-r)==0){
if(p[l]==-NM)
{
return father_of_all;
}
return p[l];
}
int mid=(l+r)/2;
bool use=0;
for(int i=l;i<=r;i++)
{
if(p[i]!=-NM)
{
use=1;
break;
}
}
if(!use)
return father_of_all;
label++;
int usep=-label;
int fk=-1;
if(!use)
{
fk=childx.size();
childx.pb(father_of_all);
childy.pb(father_of_all);
}
else
{
int lc=label_it(p,l,mid,1);
int rc=label_it(p,mid+1,r,1);
fk=childx.size();
childx.pb(lc);
childy.pb(rc);
}
order_.pb(fk);
npp.pb(usep);
return usep;
}
vll child_[NM];
ll fake_id=0,state[NM],req_sz=0;
int label_it_fake(vll&p,int l,int r,bool lp=0)
{
// cout<<"Range "<<l<<' '<<r<<' '<<" p: ";
// for(int i=l;i<=r;i++)
// {
// cout<<p[i]<<' ';
// }
// cout<<endl;
if((l-r)==0){
if(p[l]==-NM)
return 0;
req_sz++;
// cout<<"Label: "<<-l-1<<endl;
return -l-1; // always negative
}
int mid=(l+r)/2;
bool use=0;
for(int i=l;i<=r;i++)
{
if(p[i]!=-NM)
{
use=1;
break;
}
}
if(!use)
return 0;
int fk=fake_id;
fake_id++;
child_[fk].clear();
state[fk]=0;
int lc=label_it_fake(p,l,mid,1);
int rc=label_it_fake(p,mid+1,r,1);
child_[fk].pb(lc);
child_[fk].pb(rc);
// cout<<"Assigned to range "<<l<<' '<<r<<' ';
// cout<<fk<<endl;
return fk;
}
vll my_order;
void generate_order(int cur)
{
if(my_order.size()==req_sz)return;
// cout<<"At "<<cur<<endl;
if(cur<0)
{
// cout<<"Pushing "<<cur<<endl;
my_order.push_back(cur);
generate_order(0);
return;
}
state[cur]=1-state[cur];
generate_order(child_[cur][1-state[cur]]);
}
bool check(int m,vector<int> a)
{
map<int,int> cnt;
int mx=0;
for(auto i:a)
{
cnt[i]++;
mx=max(mx,cnt[i]);
}
return (mx<=4);
}
void subtask(int m, std::vector<int> a)
{
vector<int> ans(m+1);
vector<int> child[m+2];
vector<int> cur;
cur.pb(0);
for(int j=0;j<a.size();j++)
cur.pb(a[j]);
cur.pb(0);
for(int j=1;j<cur.size();j++)
child[cur[j-1]].push_back(cur[j]);
vector<int> x,y;
int s=0;
for(int i=0;i<=m;i++)
{
if(child[i].size()==1)
{
ans[i]=child[i][0];
}
else if(child[i].size()==2) // solve atmost 2
{
// We need
s++;
ans[i]=-s;
x.pb(child[i][0]);
y.pb(child[i][1]);
}
else if(child[i].size()==3)
{
int s1=s+1;
int s2=s+2;
int s3=s+3;
s+=3;
ans[i]=-s1;
// s1
x.pb(-s2);
y.pb(-s3);
//s2
x.pb(-s1);
y.pb(child[i][1]);
//s3
x.pb(child[i][0]);
y.pb(child[i][2]);
}
else if(child[i].size()==4)
{
int s1=s+1;
int s2=s+2;
int s3=s+3;
s+=3;
ans[i]=-s1;
// s1
x.pb(-s2);
y.pb(-s3);
//s2
x.pb(child[i][0]);
y.pb(child[i][2]);
//s3
x.pb(child[i][1]);
y.pb(child[i][3]);
}
}
// for(int i=0;i<=m;i++)
// {
// cout<<ans[i]<<' ';
// }
// cout<<endl;
// for(int i=0;i<s;i++)
// {
// cout<<x[i]<<' '<<y[i]<<endl;
// }
answer(ans,x,y);
}
void create_circuit(int m, std::vector<int> a)
{
// if(check(m,a))
// {
// subtask(m,a);
// return;
// }
XP.clear();
YP.clear();
label=0;
vector<int> ans(m+1);
vector<int> child[m+2];
{
int v=a[0];
child[0].push_back(v);
for(int j=1;j<a.size();j++)
child[v].push_back(a[j]);
child[v].push_back(0);
int lps=0;
for(int j=0;j<=m;j++)
ans[j]=-1;
// cout<<"SZ: "<<child[v].size()<<endl;
for(auto i:{0,v})
{
if(child[i].size()==0)continue;
if(child[i].size()==1)
{
ans[i]=child[i][0];
}
else
{
int zxp=child[i].size();
ll pw=1;
while(pw<zxp)
pw*=2;
vll fl(pw);
int cpp=0;
for(int j=zxp;j<pw;j++)
fl[cpp]=-NM,cpp++;
for(int j=0;j<zxp;j++)
fl[cpp]=child[i][j],cpp++;
// cout<<"For "<<i<<endl;
// cout<<"Before\n";
// for(int j=0;j<pw;j++)
// {
// cout<<fl[j]<<' ';
// }
// cout<<endl;
father_of_all=-label-1;
childx.clear();
childy.clear();
order_.clear();
npp.clear();
ll og=label;
father_of_all=-label-1;
// pw then
// cout<<"Father "<<father_of_all<<endl;
// cout<<"Do label\n";
childx.clear();
childy.clear();
order_.clear();
npp.clear();
req_sz=0;
my_order.clear();
fake_id=0;
int root=label_it_fake(fl,0,pw-1);
// cout<<"Made the fake tree\n";
// for(int j=0;j<fake_id;j++)
// {
// cout<<"Had node "<<j<<endl;
// cout<<"Adj: ";
// for(auto k:child_[j])
// {
// cout<<k<<' ';
// }
// cout<<endl;
// }
generate_order(root);
// cout<<"My Order: ";
// for(auto j:my_order)
// cout<<j<<' ';
// cout<<endl;
// cout<<"Req order: ";
// for(auto j:child[i])
// {
// cout<<j<<' ';
// }
// cout<<endl;
for(int i=0;i<pw;i++)fl[i]=-NM;
for(int k=0;k<child[i].size();k++)
{
fl[-my_order[k]-1]=child[i][k];
}
// cout<<"After\n";
// for(int i=0;i<pw;i++)
// {
// cout<<fl[i]<<' ';
// }
// cout<<endl;
// cout<<"Size "<<order_.size()<<endl;
label_it(fl,0,pw-1);
ll last=XP.size();
for(int i=0;i<order_.size();i++)
{
XP.pb(0);
YP.pb(0);
}
for(int i=0;i<order_.size();i++)
{
ll cur=-og-npp[i]-1;
XP[last+cur]=(childx[i]);
YP[last+cur]=(childy[i]);
}
ans[i]=father_of_all;
}
}
// cout<<"ans\n";
// for(int i=0;i<=m;i++)
// {
// cout<<i<<' '<<ans[i]<<' '<<'Z'<<endl;;
// }
// cout<<endl;
// cout<<"xy\n";
// cout<<XP.size()<<endl;
// cout<<YP.size()<<endl;
// for(auto i:XP)
// {
// cout<<i<<' ';
// }
// cout<<endl;
// for(auto i:YP)
// {
// cout<<i<<' ';
// }
// cout<<endl;
// for(int i=0;i<label;i++)
// {
// cout<<-i-1<<' '<<XP[i]<<' '<<'X'<<endl;
// cout<<-i-1<<' '<<YP[i]<<' '<<'Y'<<endl;
// // cout<<XP[i]<<' '<<YP[i]<<endl;
// }
answer(ans,XP,YP);
}
}
