#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100100;
const int INF = 123456;
const int SELF = 123321;
vector<int> X, Y;
vector<int> neigh[MAXN];
bool secondTime[MAXN];
int sCount = -1;
int createSwitch(int x, int y) {
X.push_back(x);
Y.push_back(y);
if (x == SELF)
X[-sCount] = sCount;
if (y == SELF)
Y[-sCount] = sCount;
return sCount--;
}
void printAns(vector<int> C, vector<int> X, vector<int> Y) {
cout << "C: ";
for (int x : C)
cout << x << " ";
cout << endl;
cout << "(X, Y): ";
for (int i = 0; i < (int)X.size(); i++) {
cout << "(" << X[i] << ", "
<< Y[i] << ") ";
}
cout << endl;
}
void create_circuit(int M, std::vector<int> A) {
vector<int> C(M + 1, INF);
A.push_back(0);
memset(secondTime, false, sizeof(secondTime));
for (int i = 0; i < (int)A.size()-1; i++) {
neigh[A[i]].push_back(A[i+1]);
}
C[0] = A[0];
for (int i = 1; i <= M; i++) {
int na = neigh[i].size();
if (na == 0) {
C[i] = 0;
} else if (na == 1) {
C[i] = neigh[i][0];
} else if (na == 2) {
C[i] = createSwitch(neigh[i][0],
neigh[i][1]);
} else if (na == 3) {
int s1 = createSwitch(neigh[i][1], neigh[i][2]);
int s2 = createSwitch(neigh[i][0], sCount-1);
int s3 = createSwitch(s2, s1);
C[i] = s3;
} else if (na == 4) {
C[i] = createSwitch(createSwitch(neigh[i][0], neigh[i][2]),
createSwitch(neigh[i][1], neigh[i][3]));
}
}
for (int i = 1; i <= M; i++) {
if (C[i] == INF)
C[i] = 0;
}
answer(C, X, Y);
}
