//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)];
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);
for(int i = 0 ; i < N ; i++)
{
int mask = ((1<<N) - 1 ) ^ (1<<i);
dp[i][mask] = INF;
}
for(int mask = (1<<N) - 1 ; mask >= 0 ; mask--)
for(int i = 0 ; i < N ; i++)
{
if(mask == (((1<<N) - 1 ) ^ (1<<i)))
continue;
dp[i][mask] = -1;
if(mask & (1<<i))
continue;
int new_mask = mask ^ (1<<i);
for(int j = 0 ; j < N ; j++)
if(!(new_mask & (1<<j)))
{
if(dist[i][j] <= dp[j][new_mask] && dist[i][j] > dp[i][mask])
{
dp[i][mask] = dist[i][j];
par[i][mask] = j;
}
}
}
for(int i = 0 ; i < N ; i++)
if(dp[i][0] != -1)
{
find_path(i,0);
break;
}
vector<int> ret;
while(!ans.empty())
{
ret.push_back(ans.top());
ans.pop();
}
return ret;
}
