#include "fun.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back

vector<int> createFunTour(int N, int Q) {
    if (N == 2) {
        return {0, 1};
    }
    int n = N;
    vector<int> path = {0};
    for (int v = 1; v < N; v++) {
        int x = attractionsBehind(0, v);
        if (x >= N / 2 + 1) {
            path.push_back(v);
        } 
    }
    vector<int> byd(path.size(), 0), D(n), used(n);
    used[0] = 1;
    for (int i = 1; i < path.size(); i++) {
        int d = hoursRequired(0, path[i]);
        D[path[i]] = d;
        used[path[i]] = 1;
        byd[d] = path[i];
    }
    int centr = byd.back();
    vector<int> ds(n);
    for (auto &u : path) used[u] = 1;
    for (int i = 0; i < n; i++) {
        if (!used[i]) ds[i] = hoursRequired(centr, i);
        else ds[i] = path.size() - 1 - D[i];
    }
    vector<int> sons;
    for (int i = 0; i < n; i++) {
        if (ds[i] == 1) sons.push_back(i);
    }
    vector<vector<int>> cmp(sons.size());
    vector<int> from(n);
    for (int i = 0; i < n; i++) {
        if (i != centr) {
            bool found = false;
            for (int j = 0; j < sons.size() - 1; j++) {
                if (attractionsBehind(i, sons[j]) > N / 2) {
                    from[i] = j;
                    found = true;
                    cmp[j].push_back(i);
                    break;
                }
            }
            if (!found) {
                from[i] = sons.size() - 1;
                cmp.back().push_back(i);
            }
        }       
    }
    for (int i = 0; i < sons.size(); i++) {
        sort(all(cmp[i]), [&](int u, int v){return ds[u] < ds[v];});
    }
    vector<int> ans = {centr};
    int curn = n;
    auto solve = [&](auto solve) -> void {
        if (cmp.size() == 2) {
            if (cmp[0].size() > cmp[1].size()) swap(cmp[0], cmp[1]);
            for (int i = 0; i < sz(cmp[1]); i++) {
                ans.pb(cmp[1][i]);
                if (i < cmp[0].size()) ans.pb(cmp[0][i]);
            }
            return;
        }
        for (int i = 0; i < 3; i++) {
            if (sz(cmp[i]) == curn / 2) {
                for (int j = 0; j < 3; j++) reverse(all(cmp[j]));
                for (int j = 1; j < curn; j++) {
                    if (j & 1) {
                        ans.pb(cmp[i].back()); cmp[i].pop_back();
                    } else {
                        vector<pair<int, int>> cands;
                        for (int j1 = 0; j1 < 3; j1++) {
                            if (j1 != i && !cmp[j1].empty()) {
                                cands.pb({cmp[j1].back(), j1});
                            }
                        }

                            if (cands.size() == 2 && ds[cands[0].first] > ds[cands[1].first]) swap(cands[0], cands[1]);
                            cmp[cands[0].second].pop_back();
                            ans.pb(cands[0].first);
                    }
                }
                return;
            }
        }
        vector<int> lasts;
        for(int i = 0; i < 3; i++) {
            assert(!cmp[i].empty());
            lasts.pb(cmp[i].back());
        }
        sort(all(lasts), [&](int i, int j){return ds[i] < ds[j];});
        int v1 = lasts[1], v2 = lasts[2];
        cmp[from[v1]].pop_back();
        cmp[from[v2]].pop_back();
        curn -= 2;
        solve(solve);
        if (from[ans.back()] != from[v1] && ds[v1] >= ds[ans[sz(ans) - 2]] && ds[v2] >= ds[ans.back()]) {
            ans.pb(v1); ans.pb(v2);
        } else {
            ans.pb(v2); ans.pb(v1);
        }
    };
    solve(solve);
    reverse(all(ans));
    return ans;
}