#include "doll.h"
#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef long long ll;
template<class T> bool umin(T& a, const T b){ if(a > b) { a = b; return true; } return false; }
template<class T> bool umax(T& a, const T b){ if(a < b) { a = b; return true; } return false; }
void create_circuit(int m, vector<int> a) {
int n = a.size();
vector<int> c(m + 1);
vector<int> cnt(m + 1);
a.insert(a.begin(), 0);
a.push_back(0);
for(int i=0;i<=n;i++){
cnt[a[i]]++;
}
vector<vector<int>> out(m + 1);
for(int i=1;i<=n+1;i++){
int x = a[i - 1], y = a[i];
//~ out[x].push_back(y);
out[x].push_back(y);
//~ if(cnt[y] == 1){
//~ out[x].push_back(y);
//~ } else {
//~ out[x].push_back(y);
//~ }
}
int last = 0;
vector<int> x_, y_;
auto get = [&](){
x_.push_back(0);
y_.push_back(0);
return ++last;
};
function<int(vector<int>&)> dfs = [&](vector<int>& a){
if((int)a.size() == 1){
return a[0];
}
//~ bool is_same = true;
vector<int> l, r;
for(int i=0;i<(int)a.size();i++){
if(i & 1) r.push_back(a[i]);
else l.push_back(a[i]);
//~ if(a[i] != a[0]) is_same = false;
}
//~ if(is_same){
//~ return a[0];
//~ }
int v = get();
if((int)a.size() & 1){
r.push_back(l.back());
l.back() = -v;
}
//~ cout<<"before: "<<dfs(l, 0)<<" "<<dfs(r, 0)<<endl;
int tmpLeft = dfs(l);
int tmpRight = dfs(r);
x_[v - 1] = tmpLeft;
y_[v - 1] = tmpRight;
//~ cout<<-v<<" "<<tmpLeft<<" "<<tmpRight<<"\n";
return -v;
};
for(int i=0;i<=m;i++){
if(!cnt[i]) continue;
if(cnt[i] == 1){
//~ cout<<i<<endl;
c[i] = out[i][0];
continue;
}
//~ dfs(a_, i);
c[i] = dfs(out[i]);
}
//~ for(int i=0;i<=m;i++){
//~ cout<<i<<" : ";
//~ for(auto x : out[i]) cout<<x<<" ";
//~ cout<<endl;
//~ }
//~ for(int i=0;i<=m;i++){
//~ cout<<c[i]<<" ";
//~ }
//~ cout<<endl;
//~ cout<<(int)x_.size()<<" "<<last<<endl;
//~ for(int i=0;i<last;i++){
//~ cout<<-(i + 1)<<" ";
//~ } cout<<endl;
//~ for(int i=0;i<last;i++){
//~ cout<<x_[i]<<" ";
//~ } cout<<endl;
//~ for(int i=0;i<last;i++){
//~ cout<<y_[i]<<" ";
//~ } cout<<endl;
//~ cout<<last<<endl;
const int maxAns = 4e5;
assert(last <= maxAns);
answer(c, x_, y_);
}
