#include<bits/stdc++.h>
using namespace std;
#define POW2(x) (1LL<<(x))
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
vector<int> AnsC, AnsX, AnsY;
struct Switch {
int Id;
bool State;
Switch *X_exit, *Y_exit;
Switch() : Id(0), State(false), X_exit(nullptr), Y_exit(nullptr) {}
};
int Switch_curId = 0;
Switch* create_Switch() {
Switch *node = new Switch();
node->Id = --Switch_curId;
AnsX.push_back(0);
AnsY.push_back(0);
return node;
}
void create_Tree(Switch *root, Switch *node, int height, int del) {
if(height == 1) {
if(del > 0) {
node->X_exit = root;
AnsX[-(node->Id + 1)] = root->Id;
}
return;
}
if(del >= POW2(height - 1)) {
node->X_exit = root;
AnsX[-(node->Id + 1)] = root->Id;
del -= POW2(height - 1);
} else {
node->X_exit = create_Switch();
AnsX[-(node->Id + 1)] = node->X_exit->Id;
create_Tree(root, node->X_exit, height - 1, del);
del = 0;
}
node->Y_exit = create_Switch();
AnsY[-(node->Id + 1)] = node->Y_exit->Id;
create_Tree(root, node->Y_exit, height - 1, del);
}
vector<vector<int>> Next;
void create_circuit(int M, std::vector<int> A) {
AnsC.assign(M + 1, 0);
Next.assign(M + 1, vector<int>());
A.push_back(0);
int N = A.size();
for(int i = 0; i < N; i++) {
Next[A[i]].push_back(A[(i + 1) % N]);
}
for(int trigger = 0; trigger <= M; trigger++) {
if(Next[trigger].size() == 1) {
AnsC[trigger] = Next[trigger][0];
} else {
int D, H = 0;
while(POW2(H) < Next[trigger].size()) {
H++;
}
D = POW2(H) - Next[trigger].size();
Switch *root = create_Switch();
AnsC[trigger] = root->Id;
create_Tree(root, root, H, D);
int Idx = 0;
for(int i = 0; i < POW2(H) - D; i++) {
Switch *node = root;
while(true) {
node->State = !node->State;
if(node->State == true) {
if(node->X_exit == nullptr) {
AnsX[-(node->Id + 1)] = Next[trigger][Idx++];
break;
}
node = node->X_exit;
} else {
if(node->Y_exit == nullptr) {
AnsY[-(node->Id + 1)] = Next[trigger][Idx++];
break;
}
node = node->Y_exit;
}
}
}
}
}
answer(AnsC, AnsX, AnsY);
}
