#include "doll.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int, int>
const int mod = 1e9 + 7;
const int mxN = 2e3 + 5;
const int mnN = 1e9 * -1;
using namespace std;
int curid = 0;
void create_circuit(int M, vector<int> A) {
A.push_back(0);
int N = A.size();
vector<int> X(N + 2), Y(N + 2), st(N + 3);
vector<int> C(M + 1);
int cur = 0;
for(int i = 0;i <= M;i++) C[i] = -1e9;
for(auto x : A){
if(C[cur] == -1e9) C[cur] = x;
else if(C[cur] < 0){
int u = C[cur];
while(1){
st[-1 * u - 1] = !st[-1 * u - 1];
if (st[-1 * u - 1])
{
if(X[-1 * u - 1] >= 0){
curid++;
X[curid - 1] = X[-1 * u - 1];
Y[curid - 1] = x;
X[-1 * u - 1] = -1 * curid;
break;
}else u = X[-1 * u - 1];
}
else
{
if (Y[-1 * u - 1] >= 0)
{
curid++;
X[curid - 1] = Y[-1 * u - 1];
Y[curid - 1] = x;
Y[-1 * u - 1] = -1 * curid;
break;
}
else u = Y[-1 * u - 1];
}
}
}else{
curid++;
X[curid - 1] = C[cur];
Y[curid - 1] = x;
C[cur] = -1 * curid;
}
cur = x;
}
for(int i = 0;i <= M;i++){
if(C[i] == -1e9) C[i] = 0;
// cout<<C[i]<<' ';
}
// cout<<'\n';
// for(int i = 1;i <= curid;i++){
// cout<<X[i - 1]<<' '<<Y[i - 1]<<'\n';
// }
answer(C, X, Y);
}
