#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
struct sw{
int id, x, y;
};
const int MAXM = 1e5;
const int MAXN = 1e6;
bool p = true;
int n, m;
int h[MAXM + 1];
vector<int> c, x, y, a, t;
unordered_set <int> el;
vector<vector<int>> nxt(MAXM + 1);
vector<sw> s;
void sw2(int i){
int id = s.size() + 1 * -1, xi = nxt[i][0], yi = nxt[i][1];
s.push_back((sw){id, xi, yi});
return;
}
void sw3(int i){
int id = s.size() + 1 * -1;
int xi = id - 1, yi = nxt[i][1];
s.push_back((sw){id, xi, yi});
id = xi, xi = nxt[i][0], yi = nxt[i][2];
s.push_back((sw){id, xi, yi});
}
void sw4(int i){
int id = s.size() + 1 * -1;
int xi = id - 1, yi = id - 2, idp = id;
s.push_back((sw){id, xi, yi});
id = xi, xi = nxt[i][0], yi = nxt[i][2];
s.push_back((sw){id, xi, yi});
id = idp - 2, xi = nxt[i][1], yi = nxt[i][3];
s.push_back((sw){id, xi, yi});
}
void swsys(int i){
int j = h[i];
if(j == 2) {
t[i] = s.size() + 1 * -1;
sw2(i);
}
if(j == 3) {
t[i] = s.size() + 1 * -1;
sw3(i);
}
if(j == 4) {
t[i] = s.size() + 1 * -1;
sw4(i);
}
}
void create_circuit(int M, std::vector<int> A) {
m = M, n = A.size(); a = A;
t = vector<int> (m + 1, 0);
//Hashing
for(int i = 0; i < n; i++) {
h[a[i]]++;
el.insert(a[i]);
if(i > 0) nxt[a[i - 1]].push_back(a[i]);
}
t[0] = a[0];
for(int i = 0; i < n - 1; i++){
if(h[a[i]] == 1) t[a[i]] = a[i + 1];
else p = false;
}
if(p) { //Subtask 1
answer(t, x, y);
return;
}
// Creating Switch contraptions
for(int i : el){
if(h[i] > 1) swsys(i);
}
x = y = vector<int>(s.size());
for(int i = 0; i < (int)s.size(); i++){
x[i] = s[i].x;
y[i] = s[i].y;
}
answer(t, x, y);
}
