#include "fun.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

typedef long long ll;
typedef double lf;

using namespace std;

const int MAXN = 1e5 + 10;

int n, q;
vector <int> res, ans;

map <pair <int, int>, int> dist, tsz;
inline int GetDist(int u, int v)
{
    if (dist[make_pair(u, v)]) return dist[make_pair(u, v)];
    return dist[make_pair(u, v)] = dist[make_pair(v, u)] = hoursRequired(u - 1, v - 1);
}
inline int GetSize(int u, int v)
{
    if (tsz[make_pair(u, v)]) return tsz[make_pair(u, v)];
    return tsz[make_pair(u, v)] = attractionsBehind(u - 1, v - 1);
}

int rt, sz[MAXN], dep[MAXN], bel[MAXN];
vector <int> son, vec[3];

inline void Solve2()
{
    if (vec[0].size() < vec[1].size()) swap(vec[0], vec[1]);
    for (int i = vec[0].size() - 1, j = vec[1].size() - 1; ~i; i--)
    {
        res.push_back(vec[0][i]);
        if (j == -1) res.push_back(rt);
        else res.push_back(vec[1][j--]);
    }
    if (res.size() != n) res.push_back(rt);
}

vector <int> createFunTour(int N, int Q)
{
    n = N, q = Q;
    if (n == 2)
    {
        res.push_back(0), res.push_back(1);
        return res;
    }
    sz[1] = n;
    for (int i = 2; i <= n; i++) sz[i] = GetSize(1, i);
    int mn = n; rt = 1;
    for (int i = 1; i <= n; i++)
        if (n - sz[i] <= n / 2 && mn > sz[i]) mn = sz[i], rt = i;
    for (int i = 1; i <= n; i++)
        if (i != rt)
        {
            dep[i] = GetDist(rt, i);
            if (dep[i] == 1) son.push_back(i);
        }
    bel[rt] = -1;
    for (int i = 1; i <= n; i++)
        if (dep[i] == 1)
        {
            for (int j = 0; j < son.size(); j++)
                if (son[j] == i) bel[i] = j;
        }
        else if (dep[i] > 1)
        {
            bel[i] = -1;
            for (int j = 0; j < son.size() - 1; j++)
                if (GetDist(i, son[j]) == dep[i] - 1) {bel[i] = j; break;}
            if (bel[i] == -1) bel[i] = son.size() - 1;
        }
    for (int i = 1; i <= n; i++)
        if (dep[i]) vec[bel[i]].push_back(i);
    for (int i = 0; i < son.size(); i++) sort(vec[i].begin(), vec[i].end(), [&](int x, int y) {return dep[x] < dep[y];});

    // cout << rt << '\n';
    // for (int i = 1; i <= n; i++) cout << bel[i] << ' '; cout << '\n';
    // for (int i = 1; i <= n; i++) cout << dep[i] << ' '; cout << '\n';

    if (son.size() == 2)
    {
        Solve2();
        for (auto x : res) ans.push_back(x - 1);
        // for (auto x : res) cout << x << " "; cout << '\n';
        return ans;
    }
    int num = n - 1, mxs; int pre = -1;
    while ((mxs = max(vec[0].size(), max(vec[1].size(), vec[2].size()))) < num - mxs)
    {
        int fr = 0, cur = 0;
        for (int i = 0; i < 3; i++)
            if (i != pre && vec[i].size() && fr < dep[vec[i].back()]) fr = dep[vec[i].back()], cur = i;
        res.push_back(vec[cur].back()), vec[cur].pop_back(), num--;
        pre = cur;
    }
    // cout << res.size() << "\n";
    // for (auto x : res) cout << x << ' '; cout << '\n';
    if (vec[0].size() < vec[1].size()) swap(vec[0], vec[1]);
    if (vec[0].size() < vec[2].size()) swap(vec[0], vec[2]);
    for (auto x : vec[2]) vec[1].push_back(x);
    sort(vec[1].begin(), vec[1].end(), [&](int x, int y) {return dep[x] < dep[y];});
    // for (auto x : vec[0]) cout << x << ' '; cout << '\n';
    // for (auto x : vec[1]) cout << x << ' '; cout << '\n';
    if (vec[1].size() == 0)
    {
        res.push_back(vec[0].back()), res.push_back(rt);
        for (auto x : res) ans.push_back(x - 1);
        // for (auto x : res) cout << x << " "; cout << '\n';
        return ans;
    }
    int fst1 = vec[0].back(), fst2 = vec[1].back();
    if (res.size() && (bel[fst1] == bel[res.back()] || (res.size() >= 2 && dep[res[res.size() - 2]] < dep[fst1])))
    {
        swap(vec[0], vec[1]);
        Solve2();
        if (res.size() != n) res.push_back(vec[1].front());
    }
    else Solve2();
    for (auto x : res) ans.push_back(x - 1);
    // for (auto x : res) cout << x << " "; cout << '\n';
    return ans;
}