#include "doll.h"
//#include "grader.cpp"
#include <iostream>
#include <map>
#include <set>
using namespace std;
const int MAXN = 5e5 + 5;
int usedSwitches = 0;
struct Switch
{
static int switchCnt;
int num;
int state;
int out[2];
Switch()
{
this->num = switchCnt;
switchCnt++;
this->state = 0;
this->out[0] = this->out[1] = MAXN;
}
};
int Switch::switchCnt = 0;
Switch s[MAXN];
bool removed[MAXN];
struct RouterOutput
{
int switchNum, outNum;
RouterOutput(){}
RouterOutput(int switchNum, int outNum)
{
this->outNum = outNum;
this->switchNum = switchNum;
}
void assignDirection(int nxt)
{
s[switchNum].out[outNum] = nxt;
}
};
struct Router
{
int root, sz, useless;
vector <RouterOutput> outs;
int removedCnt = 0;
Router(){}
Router(int sz, int useless)
{
usedSwitches++;
this->root = usedSwitches;
this->sz = sz;
this->useless = useless;
build(root, 0, sz-1);
optimize(root);
initOuts();
}
void optimize(int sInd)
{
//cout << sInd << " -> " << s[sInd].out[0] << '\n';
if(s[sInd].out[0]==MAXN)
{
if(useless>=2)
{
useless -= 2;
removed[sInd] = 1;
//cout << "remove*: " << sInd << '\n';
removedCnt++;
}
return;
}
optimize(-s[sInd].out[0]);
optimize(-s[sInd].out[1]);
if(removed[ -s[sInd].out[0] ]==true && removed[ -s[sInd].out[1] ]==true)
{
//cout << "remove: " << sInd << '\n';
removed[sInd] = 1;
removedCnt++;
}
else if(removed[ -s[sInd].out[0] ]==true)
{
s[sInd].out[0] = -root;
}
else if(removed[ -s[sInd].out[1] ]==true)
{
s[sInd].out[1] = -root;
}
}
void build(int sInd, int l, int r)
{
//cout << sInd << " || " << l << " " << r << '\n';
if(l+1==r) return;
if(l+2==r)
{
usedSwitches++;
s[sInd].out[0] = -usedSwitches;
return;
}
usedSwitches++;
s[sInd].out[0] = -usedSwitches;
usedSwitches++;
s[sInd].out[1] = -usedSwitches;
build(-s[sInd].out[0], l, (l+r)/2);
build(-s[sInd].out[1], (l+r)/2+1, r);
}
void initOuts()
{
for(int i = 0;i<sz;i++)
{
int sInd = root;
while(true)
{
if(s[sInd].out[ s[sInd].state ]==MAXN)
{
outs.push_back(RouterOutput(sInd, s[sInd].state));
s[sInd].state ^= 1;
break;
}
s[sInd].state ^= 1;
sInd = -s[sInd].out[ s[sInd].state^1 ];
}
}
//if(outs.size()!=sz) answer({}, {}, {});
//for(RouterOutput x: outs) cout << x.switchNum << " &&& " << x.outNum << '\n';
}
};
Router r[MAXN];
vector <int> nxt[MAXN];
void relabel(vector <int> &c, vector <int> &x, vector <int> &y)
{
set <int> s;
for(int i = 1;i<=usedSwitches;i++)
{
if(removed[i]==false) s.insert(i);
}
map <int, int> mp;
//cout << x.size() << '\n';
//for(int i = 0;i<x.size();i++) cout << x[i] << " " << y[i] << '\n';
//cout << '\n' << '\n';
int ind = 0;
for(int a: s)
{
ind++;
mp[-a] = -ind;
//cout << a << " vs " << ind << '\n';
swap(x[a-1], x[ind-1]);
swap(y[a-1], y[ind-1]);
}
for(int &b: c)
{
if(b<0) b = mp[b];
}
for(int &b: x)
{
if(b<0) b = mp[b];
}
for(int &b: y)
{
if(b<0) b = mp[b];
}
while(x.size()!=ind) x.pop_back(), y.pop_back();
//cout << x.size() << '\n';
//for(int i = 0;i<x.size();i++) cout << x[i] << " " << y[i] << '\n';
}
void create_circuit(int M, vector <int> A)
{
vector <int> C(M+1);
if(A.size()==1)
{
C[0] = A[0];
C[ A[0] ] = 0;
answer(C, {}, {});
return;
}
A.push_back(0);
for(int i = 0;i<A.size()-1;i++) nxt[ A[i] ].push_back(A[i+1]);
int sz = 1;
while(sz<A.size()-1) sz *= 2;
Router R = Router(sz, sz-(A.size()-1));
C[0] = A[0];
for(int i = 1;i<=M;i++) C[i] = -1;
int useLess = R.useless;
for(int i = 0;i<useLess;i++) R.outs[i].assignDirection(-R.root);
for(int i = 0;i<A.size()-1;i++)
{
R.outs[useLess+i].assignDirection(A[i+1]);
}
vector <int> X(usedSwitches), Y(usedSwitches);
for(int i = 1;i<=usedSwitches;i++)
{
X[i-1] = s[i].out[0];
Y[i-1] = s[i].out[1];
//cout << X[i-1] << " " << Y[i-1] << '\n';
}
relabel(C, X, Y);
answer(C, X, Y);
}
/*
4 4
1 2 1 3
4 7
1 3 4 2 1 2 2
1 12
1 1 1 1 1 1 1 1 1 1 1 1
5 11
1 2 5 2 3 4 1 2 5 5 4
5 4
1 1 1 1
*/
