#include "doll.h" #include <bits/stdc++.h> using namespace std; void create_circuit(int M, vector<int> A) { int N = A.size(); A.push_back(0); vector<int> C(M + 1); vector<int> X, Y; vector<vector<int>> edge(M + 1); for (int i = 0; i < N; i++) { edge[A[i]].push_back(A[i + 1]); } C[0] = A[0]; for (int m = 1; m <= M; m++) { if (edge[m].empty()) {} else if (edge[m].size() == 1) { C[m] = edge[m][0]; } else { int L = edge[m].size(); int b = 32 - __builtin_clz(L - 1); int K = (1 << b); C[m] = -X.size() - 1; int xsz = X.size(); vector<bool> rem(K + 1); vector<pair<int, int>> swt(K + 1); for (int i = 1, l = b - 1; l >= 0; l--, i = i + i + 1) { if ((K - L) & (1 << l)) { swt[i].first = -1; int ll = i + i, rr = ll + 1; for (int c = 0; c < l; c++, ll += ll, rr += rr) { for (int j = ll; j < rr; j++) { rem[j] = true; swt[j].first = swt[j].second = -1; } } } } int idx = xsz + 1; vector<int> nid(K + 1); for (int i = 1; i <= K; i++) { if (!rem[i]) { nid[i] = idx++; } } vector<int> v; for (int i = 0; i < K; i++) { bitset<32> bs(i); for (int j = 0; j < b / 2; j++) { bool t = bs[j]; bs[j] = bs[b - j - 1]; bs[b - j - 1] = t; } v.push_back(bs.to_ulong()); } for (int i = 0, k = K / 2; i < K; i += 2, k++) { if (swt[k].first == -1) { v[i] = 1e9; } if (swt[k].second == -1) { v[i + 1] = 1e9; } } vector<int> stv = v; sort(stv.begin(), stv.end()); for (int i = 0; i < K; i++) { if (v[i] != 1e9) { v[i] = lower_bound(stv.begin(), stv.end(), v[i]) - stv.begin(); } } vector<int> xid, yid; for (int i = 0, k = K / 2; k < K; i += 2, k++) { if (swt[k].first != -1) { xid.push_back(v[i]); } if (swt[k].second != -1) { yid.push_back(v[i + 1]); } } reverse(xid.begin(), xid.end()); reverse(yid.begin(), yid.end()); for (int i = 1; i < K / 2; i++) { if (!rem[i]) { if (swt[i].first != -1) { X.push_back(-nid[i + i]); } else { X.push_back(-xsz - 1); } if (swt[i].second != -1) { Y.push_back(-nid[i + i + 1]); } else { Y.push_back(-xsz - 1); } } } for (int i = K / 2; i < K; i++) { if (!rem[i]) { if (swt[i].first != -1) { X.push_back(edge[m][xid.back()]); xid.pop_back(); } else { X.push_back(-xsz - 1); } if (swt[i].second != -1) { Y.push_back(edge[m][yid.back()]); yid.pop_back(); } else { Y.push_back(-xsz - 1); } } } Y.back() = edge[m][L - 1]; } } map<int, int> mp; for (int i = 0; i < X.size(); i++) { if (X[i] == Y[i]) { mp[-i - 1] = X[i]; } } for (int &x : C) { if (mp.count(x)) { x = mp[x]; } } for (int &x : X) { if (mp.count(x)) { x = mp[x]; } } for (int &x : Y) { if (mp.count(x)) { x = mp[x]; } } vector<int> nX, nY; map<int, int> nid; for (int i = 0; i < X.size(); i++) { if (!mp.count(-i - 1)) { nid[-i - 1] = -nX.size() - 1; nX.push_back(X[i]); nY.push_back(Y[i]); } } for (int &x : C) { if (nid.count(x)) { x = nid[x]; } } for (int &x : nX) { if (nid.count(x)) { x = nid[x]; } } for (int &x : nY) { if (nid.count(x)) { x = nid[x]; } } X = nX, Y = nY; answer(C, X, Y); }