#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
/*
void answer(vector <int> c,vector <int> x,vector <int> y){
cout<<"C: ";
for (auto&i:c) cout<<i<<' ';
cout<<endl;
cout<<"X: ";
for (auto&i:x) cout<<i<<' ';
cout<<endl;
cout<<"Y: ";
for (auto&i:y) cout<<i<<' ';
cout<<endl;
return;
}
*/
void create_circuit(int m,vector <int> a){
int n=a.size();
vector <int> nxt[m+1];
a.push_back(0);
for (int i=0; i<n; i++){
nxt[a[i]].push_back(a[i+1]);
}
bool ok=1;
for (int i=1; i<=m; i++){
//for (auto&j:nxt[i]) cout<<j<<' ';
//cout<<endl;
if (nxt[i].size()>4){
ok=0;
break;
}
}
vector <int> c(m+1,0),x,y;
int cur=0;
if (ok){
c[0]=a[0];
map <int,int> p;
for (int i=1; i<=n; i++){
if (nxt[a[i-1]].size()==1){
c[a[i-1]]=a[i];
} else if (nxt[a[i-1]].size()==2){
if (p.count(a[i-1])) c[a[i-1]]=p[a[i-1]];
else {
cur--;
p[a[i-1]]=cur;
c[a[i-1]]=cur;
x.push_back(nxt[a[i-1]][0]);
y.push_back(nxt[a[i-1]][1]);
}
} else if (nxt[a[i-1]].size()==3){
if (p.count(a[i-1])) c[a[i-1]]=p[a[i-1]];
else {
cur--;
p[a[i-1]]=cur;
c[a[i-1]]=cur;
x.push_back(cur-1);
y.push_back(cur-2);
cur--;
x.push_back(nxt[a[i-1]][0]);
y.push_back(nxt[a[i-1]][1]);
cur--;
x.push_back(nxt[a[i-1]][2]);
y.push_back(cur+2);
}
} else if (nxt[a[i-1]].size()==4){
if (p.count(a[i-1])) c[a[i-1]]=p[a[i-1]];
else {
cur--;
p[a[i-1]]=cur;
c[a[i-1]]=cur;
x.push_back(cur-1);
y.push_back(cur-2);
cur--;
x.push_back(nxt[a[i-1]][0]);
y.push_back(nxt[a[i-1]][2]);
cur--;
x.push_back(nxt[a[i-1]][1]);
y.push_back(nxt[a[i-1]][3]);
}
}
}
}
answer(c,x,y);
return;
}
/*
int main(){
int n,m;
cin>>n>>m;
vector <int> a;
for (int i=0; i<n; i++){
int t;
cin>>t;
a.push_back(t);
}
create_circuit(m,a);
}
*/
