#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
int n;
int depth[MAXN];
vector<int> adj;
vector<int> groups[5];
bool cmp(int i, int j) { return depth[i] < depth[j]; }
bool hasMajoritary()
{
int mx = 0;
int sum = 0;
for(int i = 0 ; i < 3 ; i++)
{
sum += (int)groups[i].size();
mx = max( mx , (int)groups[i].size() );
}
return ( sum - mx <= mx );
}
int getCentroid()
{
int sub = n;
int cent = 0;
for(int i = 1 ; i < n ; i++)
{
int curSub = attractionsBehind( 0 , i );
if( curSub > n/2 && curSub < sub )
{
cent = i;
sub = curSub;
}
}
return cent;
}
void findGroups()
{
int degree = 0;
for(int i = 0 ; i < n ; i++)
{
if( depth[i] == 1 )
{
adj.push_back( i );
groups[degree++].push_back( i );
}
}
for(int i = 0 ; i < n ; i++)
{
if( depth[i] <= 1 ) continue;
int distA = hoursRequired( i , adj[0] );
int distB = hoursRequired( i , adj[1] );
if( distA < distB ) groups[0].push_back( i );
if( distA > distB ) groups[1].push_back( i );
if( distA == distB ) groups[2].push_back( i );
}
for(int i = 0 ; i < degree ; i++)
sort( groups[i].begin() , groups[i].end() , cmp );
}
int getMajoritary()
{
int maj = 0;
for(int i = 0 ; i < 3 ; i++)
if( (int)groups[maj].size() <= (int)groups[i].size() ) maj = i;
return maj;
}
vector<int> createFunTour(int N, int Q)
{
n = N;
if( N == 2 )
{
vector<int> ans = { 0 , 1 };
return ans;
}
int cent = getCentroid();
depth[cent] = 0;
for(int i = 0 ; i < N ; i++)
if( i != cent ) depth[i] = hoursRequired( cent , i );
findGroups();
int first = 0;
vector<int> ans;
int last = -1;
while( !hasMajoritary() )
{
int nxt = 0;
if( last == 0 ) nxt = 1;
for(int i = 0 ; i < 3 ; i++)
{
if( last == i ) continue;
if( depth[ groups[nxt].back() ] <= depth[ groups[i].back() ] )
nxt = i;
}
last = nxt;
ans.push_back( groups[nxt].back() );
groups[nxt].pop_back();
}
int indMajoritary = getMajoritary();
if( last != -1 )
{
int otherGroup = 3 - last - indMajoritary;
if( depth[ ans.back() ] <= depth[ groups[otherGroup].back() ] )
first = 1;
}
if( indMajoritary != 0 )
swap( groups[0] , groups[indMajoritary] );
while( !groups[2].empty() )
{
groups[1].push_back( groups[2].back() );
groups[2].pop_back();
}
sort( groups[1].begin() , groups[1].end() , cmp );
for(int i = 1 ; i <= 3*N ; i++)
{
if( !groups[first].empty() )
{
ans.push_back( groups[first].back() );
groups[first].pop_back();
}
if( !groups[1 - first].empty() )
{
ans.push_back( groups[1 - first].back() );
groups[1 - first].pop_back();
}
}
ans.push_back( cent );
return ans;
}
