//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);
vector<int> adj[100005];
int n,dist[505][505],dp[20][(1<<19)],par[20][(1<<19)];
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;
void find_path(int i,int mask)
{
ans.push(i);
int j = par[i][mask];
int new_mask = mask ^ (1<<i);
if(new_mask == (1<<n) - 1)
return;
find_path(j,new_mask);
}
std::vector<int> createFunTour(int N, int Q)
{
n = N;
int H = hoursRequired(0, N - 1);
int A = attractionsBehind(0, N - 1);
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);
vector<int> ret;
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;
}
