#include "doll.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
#define pb push_back
#define F first
#define S second
#define _ <<" "<<
#define pii pair < int , int >
using namespace std;
struct seg_tree{
vector < int > t, num;
vector < bool > l, r;
int n, len, how = 1, bad = 0;
seg_tree(){n = len = 0;};
seg_tree(int _n){
n = _n;
len = 1;
while(len <= n) len <<= 1;
t.resize(len << 1 | 1);
l.resize(len << 1 | 1);
r.resize(len << 1 | 1);
num.resize(len << 1 | 1);
for (int i = 0; i < num.size(); ++i)
num[i] = i;
};
void way(int v, int tl, int tr){
if (!t[v]){
t[v] = 2;
} else
if (t[v] == 1) t[v] = 2; else t[v] = 1;
if (tl == tr){
t[v] = how++;
return;
}
int tm = (tl + tr) >> 1;
if (t[v] == 1){
way(v << 1, tl, tm);
l[v] = 1;
}else{
way(v << 1 | 1, tm + 1, tr);
r[v] = 1;
}
}
};
vector < int > g[(int)(1e5 + 5)];
void create_circuit (int m, vector < int > a) {
int n = a.size();
a.pb(0);
vector < int > c;
for (int i = 1; i <= n; ++i){
// cout << a[i - 1] << endl;
g[a[i - 1]].pb(a[i]);
}
g[0].pb(a[0]);
int now = 1;
vector < pii > swit;
cerr << TIME << endl;
for (int i = 0; i <= m; ++i){
int sz = g[i].size();
if (!sz){
c.pb(0);
continue;
}
if (sz == 1){
c.pb(g[i][0]);
} else {
vector < int > all;
for (int j = 0; j < sz; ++j) all.pb(g[i][j]);
seg_tree t;
t = seg_tree(sz);
int cnt = 0;
for (int i = 0; i < sz; ++i){
t.way(1, 0, t.len - 1);
}
vector < int > vis;
vector < int > q;
reverse(all.begin(), all.end());
int good[t.t.size() + 1];
int val[t.t.size() + 1];
fill(good, good + t.t.size(), 1);
for (int i = t.t.size() - 1; i >= 1; --i)
if (t.t[i]){
if (!t.r[i]){
t.num[i] = -all[t.t[i] - 1];
val[i] = t.num[i];
continue;
}
if (t.l[i] && val[i << 1] != val[i << 1 | 1]) good[i] = 0; else val[i] = val[i << 1 | 1];
if (!t.l[i])
t.num[i << 1] = 1;
if (!good[i << 1] || !good[i << 1 | 1]) good[i] = 0;
// cout << i _ good[i] << endl;
if (good[i]) t.num[i] = t.num[i << 1 | 1];
}
for (int i = 1; i < t.t.size(); ++i)
if (t.t[i]){
if (!t.r[i]){
t.num[i] = -all[t.t[i] - 1];
continue;
}
if (good[i]){
if (good[i] == 3){
if ((i << 1) < t.t.size())
good[i << 1] = good[i << 1 | 1] = 3;
continue;
}
good[i << 1] = good[i << 1 | 1] = 3;
t.num[i << 1 | 1] = 1;
}
vis.pb(i);
q.pb(i);
if (t.num[i << 1] > 0) q.pb(t.num[i << 1]);
if (t.num[i << 1 | 1] > 0) q.pb(t.num[i << 1 | 1]);
}
reverse(vis.begin(), vis.end());
sort(q.begin(), q.end());
q.resize(unique(q.begin(), q.end()) - q.begin());
unordered_map < int , int > mp;
reverse(vis.begin(), vis.end());
for (int i : q) mp[i] = now++;
for (int i : vis){
int f = t.num[i << 1];
if (mp.count(f)) f = mp[f];
int s = t.num[i << 1 | 1];
if (mp.count(s)) s = mp[s];
swit.pb({-f, -s});
// cout << i _ -f _ -s _ good[i] << endl;
}
// cout << vis.size() _ now << endl;
// for (int i = 1; i < t.num.size(); ++i)
// cout << t.num[i] _ t.t[i] _ t.l[i] _ t.r[i] << endl;
// for (auto i : swit)
// cout << i.F _ i.S << endl;
c.pb(-mp[t.num[1]]);
}
}
cerr << TIME << endl;
// for (int i : c) cout << i << " ";
// cout << endl;
vector < int > X, Y;
for (int i = 0; i < swit.size(); ++i){
X.pb(swit[i].F), Y.pb(swit[i].S);
// cout << X.back() _ Y.back() << endl;
}
answer(c, X, Y);
}
