#include "doll.h"
#include<algorithm>
#include<iostream>
#include<vector>
#include<iomanip>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
void print(vi &L) {
cerr << "{";
for (auto i : L) cerr << i << ", ";
cerr << "}" << endl;
}
void create_circuit(int m, vector<int> A) {
int n = A.size();
A.push_back(0);
vi C(m + 1, 0);
vi X, Y;
int l = 0;
for (int i = 0; i <= n; i++) {
/*
cerr << "iteration : " << i << endl;
cerr << "C : ";
print(C);
cerr << "X : ";
print(X);
cerr << "Y : ";
print(Y);
//*/
if (C[l] == 0) {
l = C[l] = A[i];
continue;
}
if (C[l] > 0) {
X.push_back(C[l]);
Y.push_back(A[i]);
C[l] = -X.size();
l = A[i];
continue;
}
int p = (-C[l])-1;
int x = X[p], y = Y[p];
if (x > 0) {
X.push_back(C[l]);
Y.push_back(y);
X[p] = -X.size();
X.push_back(x);
Y.push_back(A[i]);
Y[p] = -X.size();
l = A[i];
continue;
}
int xp = -x-1, yp = -y-1;
int a1 = X[yp], a2 = Y[xp], a3 = Y[yp], a4 = A[i];
X[xp] = a1; X[yp] = a2; Y[xp] = a3; Y[yp] = a4;
l = a4;
}
answer(C, X, Y);
}
