#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
int n,q;
int find_cen(){
    vector<pair<int,int>> a;
    for(int i = 1;i < n;i++){
        int s = attractionsBehind(0,i); 
        if(s*2 >= n){
            a.emplace_back(s,i);
        }
    }
    if(a.empty()) return 0;
    sort(a.begin(),a.end());
    return a[0].second;
}
const int N = 1e5 + 12;
int val[N];
vector<int> createFunTour(int nn, int qq) {
    if(nn == 2){
        return {0,1};
    }
    n = nn;q = qq;
    int c = find_cen();
    array<int,3> ver = {-1,-1,-1};
    array<vector<pair<int,int>>,3> vec;
    for(int i = 0;i < n;i++){
        if(i == c) continue;
        val[i] = hoursRequired(c,i);
        if(val[i] == 1){
            for(int j = 0;j < 3;j++){
                if(ver[j] == -1){
                    ver[j] = i;
                    break;
                }
            }
        }
    }
    vector<int> res;
    for(int i = 0;i < n;i++){
        if(i == c) continue;
        if(val[i] == 1){
            if(i == ver[0]){
                vec[0].push_back({1,i});
            }else if(i == ver[1]){
                vec[1].push_back({1,i});
            }else{
                vec[2].push_back({1,i});
            }
            continue;
        }
        int _ = -1;
        for(int k = 0;k < 2;k++){
            if(val[i] - 1 == hoursRequired(i,ver[k])){
                _=k;
                break;
            }
        }
        if(_ == -1) _ = 2;
        vec[_].push_back({val[i],i});
    }
    int lst = -1;
    for(int i = 0;i < 3;i++){
        sort(vec[i].begin(),vec[i].end());
    }
    vector<int> io;
    for(int i = 0;i < n;i++){
        io.push_back(i);
    }
    while(true){
        int _x = (int)vec[0].size(),_y = (int)vec[1].size(),_z = (int)vec[2].size();
        if(_x == _y + _z || _y == _x + _z || _z == _x + _y){
            break;
        }
        if(!_x || !_y || !_z){
            int mx = max({_x,_y,_z});
            for(int i = 0;i < 3;i++){
                if((int)vec[i].size() == mx){
                    lst = i;
                    res.push_back(vec[i].back().second);
                    vec[i].pop_back();
                    break;
                }else{
                    assert((int)vec[i].size() == 0 || (int)vec[i].size() == mx - 1);
                }
            }
            break;
        }
        pair<int,int> mx = {-1,-1};
        int id = -1;
        auto upd = [&](vector<pair<int,int>> &a,int j){
            if(j != lst && (int)a.size()){
                pair<int,int> nv = make_pair(a.back().first,(int)a.size());
                if(nv > mx){
                    mx = nv;
                    id = j;
                }
            }
        };
        auto del = [&](vector<pair<int,int>> &x){ 
            res.push_back(x.back().second);
            x.pop_back();
        };
        int cc = 0;
        for(int i = 0;i < 3;i++){
            if((int)vec[i].empty()) cc++;
            upd(vec[i],i);
        }
        lst = id;
        del(vec[id]);
    }
    vector<int> X,Y;
    vector<pair<int,int>> bff;
    for(int i = 0;i < 3;i++){
        bff.push_back({(int)vec[i].size(),i});
    }
    sort(bff.begin(),bff.end());
    bool ok = false;
    for(int i = 0;i < 3;i++){
        int j = bff[i].second;
        if(i < 2){
            if(lst == j) ok = 1;
            for(auto f:vec[j]){
                X.push_back(f.second);
            }
        }else{
            for(auto f:vec[j]){
                Y.push_back(f.second);
            }
        }
    }
    if(ok){
        X.swap(Y);
    }
    auto cmp = [&](int x,int y)->bool{
        return val[x] > val[y];
    };
    sort(X.begin(),X.end(),cmp);
    sort(Y.begin(),Y.end(),cmp);
    for(int i = 0;i < (int)X.size();i++){
        res.push_back(X[i]);
        res.push_back(Y[i]);
    }
    res.push_back(c);
    return res;
}