#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5, maxm = 1e5 + 5, maxN = 4e5 + 5;
int n, m;
vector<int> a;
int cnt = 0;
vector<int> adj[maxm];
vector<int> nxt, l, r;
bool on[maxN];
void build(int u, int sz) {
if (sz == 1) return;
l.push_back(0), r.push_back(0);
l.push_back(0), r.push_back(0);
cnt--, l[-u-1] = cnt;
cnt--, r[-u-1] = cnt;
build(l[-u-1], sz-1); build(r[-u-1], sz-1);
}
void create_circuit(int M, vector<int> A) {
m = M, a = A;
n = a.size();
for (int i=0;i<n-1;i++) adj[a[i]].push_back(a[i+1]);
adj[a[n-1]].push_back(0);
nxt.resize(m+1);
nxt[0] = a[0];
for (int i=1;i<=m;i++) {
// cout << i << endl;
if (adj[i].size()==0) continue;
if (adj[i].size()==1) {
nxt[i] = adj[i][0];
continue;
}
cnt--;
l.push_back(0), r.push_back(0);
// cout << cnt << " " << l.size() << " " << r.size() << endl;
int rt = cnt;
nxt[i] = cnt;
int sz = log2(adj[i].size() - 1) + 1;
build(rt, sz);
sz = (1<<sz);
int delta = sz - adj[i].size();
// cout << delta << endl;
// cout << i << endl;
// for (int x:adj[i]) cout << x << " "; cout << endl;
for (int j=0;j<sz;j++) {
int u = rt;
while (l[-u-1] != 0 && r[-u-1] != 0) {
if (on[-u-1]) {
on[-u-1] = !on[-u-1];
u = r[-u-1];
} else {
on[-u-1] = !on[-u-1];
u = l[-u-1];
}
}
// cout << u << " " << on[u] << " " << j << " " << j-delta << " " << adj[i][j-delta] << endl;
if (on[-u-1]) {
on[-u-1] = !on[-u-1];
if (j-delta < 0) r[-u-1] = rt;
else r[-u-1] = adj[i][j-delta];
} else {
on[-u-1] = !on[-u-1];
if (j-delta < 0) l[-u-1] = rt;
else l[-u-1] = adj[i][j-delta];
}
}
// cout << l.size() << endl;
// for (int j=0;j<l.size();j++) cout << l[j] << " " << r[j] << endl;
}
// cout << l.size() << endl;
// for (int i=0;i<l.size();i++) cout << l[i] << " " << r[i] << endl;
// int u = 0;
// while (true) {
// // if (u>=0) cout << u << endl;
// if (u>=0) u = nxt[u];
// else if (on[-u-1]) {
// on[-u-1] = !on[-u-1];
// u = r[-u-1];
// } else {
// on[-u-1] = !on[-u-1];
// u = l[-u-1];
// }
// if (u==0) break;
// }
answer(nxt, l, r);
}
