#include "doll.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
int switches=0;
vector<int>copii[400005];
int out[400005];
int fiu1[400005];
int fiu2[400005];
vector<int>indicii;
void solve(int node,int sz,vector<int>vec,int index,int pw)
{
if(sz==2)
{
indicii.push_back(index);
indicii.push_back(index+pw);
return;
}
int mij=(sz)/2;
vector<int>st;
vector<int>dr;
int f1=0,f2=0;
for(int i=0;i<vec.size();i++)
{
if(vec[i]<0)
{
if(st.size()<mij)
{
f1++;
st.push_back(vec[i]);
}
else
{
f2++;
dr.push_back(vec[i]);
}
}
else
{
if(dr.size()<st.size())
{
dr.push_back(vec[i]);
}
else
{
st.push_back(vec[i]);
}
}
}
if(f1!=mij)
{
switches++;
fiu1[-node]=-switches;
solve(fiu1[-node],mij,st,index,pw*2);
}
else
{
fiu1[-node]=vec[0];
}
switches++;
fiu2[-node]=-switches;
solve(fiu2[-node],mij,dr,index+pw,pw*2);
}
void add(int node,int index,int val,int st,int dr)
{
if(st+1==dr)
{
if(index==0)
{
fiu1[-node]=val;
}
else
{
fiu2[-node]=val;
}
return;
}
int mij=(st+dr)/2;
if(index%2==0)
{
add(fiu1[-node],index/2,val,st,mij);
}
else
{
add(fiu2[-node],index/2,val,mij+1,dr);
}
}
void make(int poz)
{
if(copii[poz].size()==0)
{
out[poz]=0;
return;
}
else if(copii[poz].size()==1)
{
out[poz]=copii[poz][0];
return;
}
else
{
indicii.clear();
switches++;
out[poz]=-switches;
int adev=copii[poz].size();
reverse(copii[poz].begin(),copii[poz].end());
while(__builtin_popcount(copii[poz].size())!=1)
{
copii[poz].push_back(out[poz]);
}
int fals=copii[poz].size()-adev;
reverse(copii[poz].begin(),copii[poz].end());
solve(out[poz],copii[poz].size(),copii[poz],0,1);
sort(indicii.begin(),indicii.end());
int off=0;
if(fals%2==1)
{
off=1;
}
else
{
off=0;
}
for(int i=fals-off;i<copii[poz].size();i++)
{
add(out[poz],indicii[i-(fals-off)],copii[poz][i],0,copii[poz].size()-1);
}
}
}
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
copii[0].push_back(A[0]);
for(int i=0;i+1<N;i++)
{
copii[A[i]].push_back(A[i+1]);
}
copii[A[N-1]].push_back(0);
vector<int>C,X,Y;
for(int i=0;i<=M;i++)
{
make(i);
C.push_back(out[i]);
//cout<<i<<" "<<out[i]<<'\n';
}
for(int i=1;i<=switches;i++)
{
X.push_back(fiu1[i]);
Y.push_back(fiu2[i]);
//cout<<-i<<" x: "<<fiu1[i]<<" y: "<<fiu2[i]<<'\n';
}
answer (C,X,Y);
}
