#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
using IntList = vector<int>;
using AdjL = vector<IntList>;
int bST(IntList &targets, IntList &exitX, IntList &exitY) {
if (targets.size() == 1) return targets[0];
int swId = -(int(exitX.size()) + 1);
exitX.emplace_back(0);
exitY.emplace_back(0);
if (targets.size() % 2 != 0) {
targets.insert(targets.end() - 2, swId);
}
IntList left, right;
for (size_t i = 0; i < targets.size(); i += 2) {
left.push_back(targets[i]);
right.push_back(targets[i + 1]);
}
exitX[-swId - 1] = bST(left, exitX, exitY);
exitY[-swId - 1] = bST(right, exitX, exitY);
return swId;
}
void create_circuit(int M, vector<int> sequence) {
int len = sequence.size();
AdjL edges(M + 1);
edges[0].push_back(sequence[0]);
for (int i = 1; i < len; ++i) {
edges[sequence[i - 1]].push_back(sequence[i]);
}
edges[sequence[len - 1]].push_back(0);
IntList conn(M + 1, 0);
IntList swX, swY;
for (int device = 0; device <= M; ++device) {
if (!edges[device].empty()) {
conn[device] = bST(edges[device], swX, swY);
}
}
answer(conn, swX, swY);
}
