#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
//#define BALBIT
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) { cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S &&...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#endif // BALBIT
const int maxn = 2e5+5;
vector<int> go[maxn];
int IT = 0; // keep indexes positive until returning
vector<int> X,Y;
vector<int> sw;
bool st[maxn*4];
bool del[maxn*4];
int par[maxn*4];
bool isx[maxn*4];
//int add(int x=0, int y=0) {
// X.pb(x); Y.pb(y);
// return ++IT;
//}
const int inf = 1000000000;
void create_circuit(int n, std::vector<int> A) {
bug("HI");
X.pb(0); Y.pb(0);
A.pb(0);
int m = SZ(A);
REP(i, m-1) {
go[A[i]].pb(A[i+1]);
}
sw.resize(n+1);
sw[0] = A[0];
REP1(i,n) {
if (SZ(go[i]) == 0) {
sw[i] = i;
continue;
}
if (SZ(go[i]) == 1) {
sw[i] = go[i][0];
continue;
}
int dep = 0;
while ((1<<dep) < SZ(go[i])) ++dep;
bug(i, SZ(go[i]), dep);
// build tree
sw[i] = -(IT+1);
int take = (1<<dep)-1;
REP(k, ((1<<dep) - SZ(go[i]))/2) --take;
REP1(j, take) {
X.pb(0); Y.pb(0);
int lc = j*2, rc = j*2+1;
if (lc < (1<<dep)) {
if (lc <= take)
X[j+IT] = -(lc+IT);
else
X[j+IT] = sw[i];
if (rc <= take)
Y[j+IT] = -(rc+IT);
else
Y[j+IT] = sw[i];
// par[(lc+IT)] = par[(rc+IT)] = j+IT;
// isx[lc+IT] = 1;
}else{
X[j+IT] = Y[j+IT] = inf;
}
swap(X[j+IT], Y[j+IT]);
}
IT += ((1<<dep)-1);
vector<int> hi;
if (SZ(go[i]) % 2 == 1) hi.pb(sw[i]);
for (int x : go[i]) hi.pb(x);
REP(j, SZ(hi)) {
int at = -sw[i];
while (1) {
int &to = st[at]?Y[at]:X[at];
st[at] ^= 1;
if (to == inf) {
to = hi[j];
break;
}else{
at = -to;
}
}
}
}
X.erase(X.begin()); Y.erase(Y.begin());
answer(sw,X,Y);
}
/*
5 9
1 2 1 3 1 4 1 5 1
*/
