//chockolateman
#include<bits/stdc++.h>
#include "fun.h"
using namespace std;
const int INF = 1e9;
int hoursRequired(int X, int Y);
int attractionsBehind(int X, int Y);
int n,dist[505][505];
vector<int> adj[100005];
set<int> distances[100005];
bool used[5005];
void dfs(int v,int p,int root)
{
for(auto u : adj[v])
if(u != p)
{
dist[root][u] = dist[root][v] + 1;
dfs(u,v,root);
}
}
stack<int> ans;
std::vector<int> createFunTour(int N, int Q)
{
n = N;
int H = hoursRequired(0, N - 1);
int A = attractionsBehind(0, N - 1);
vector<int> ret;
if(n <= 500)
{
for(int i = 0 ; i < N ; i++)
for(int j = i+1 ; j < N ; j++)
{
if(hoursRequired(i, j) == 1)
{
adj[i].push_back(j);
adj[j].push_back(i);
}
}
for(int i = 0 ; i < N ; i++)
dfs(i,i,i);
int cur_dist = 0;
int i,j;
for(int x = 0 ; x < N ; x++)
for(int y = x+1 ; y < N ; y++)
if(dist[x][y] > cur_dist)
{
i = x;
j = y;
cur_dist = dist[x][y];
}
ret.push_back(i);
ret.push_back(j);
int prev = j;
used[i] = true;
used[j] = true;
int counter = 2;
while(counter < N)
{
int prev_dist = cur_dist;
int y = 1;
cur_dist = 0;
for(int x = 0 ; x < N ; x++)
if(!used[x] && dist[prev][x] <= prev_dist && dist[prev][x] >= cur_dist)
{
y = x;
cur_dist = dist[prev][x];
}
ret.push_back(y);
prev = y;
used[y] = true;
counter++;
}
}
return ret;
}
