#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=305;
int qrs[nx][nx], vs[nx], m, cnt, u, v;
vector<int> d[nx];
int query(int i, int j)
{
if (i>j) swap(i, j);
return qrs[i][j];
}
void dfs(int u)
{
vs[u]=1;
cnt++;
for (auto v:d[u]) if (!vs[v]) dfs(v);
}
std::vector<int> longest_trip(int N, int D)
{
for (int i=0; i<N; i++) d[i].clear(), vs[i]=0;
for (int i=0; i<N; i++) for (int j=i+1; j<N; j++) qrs[i][j]=are_connected(vector<int> {i}, vector<int> {j});
for (int i=0; i<N; i++) for (int j=0; j<N; j++) if (query(i, j)) d[i].push_back(j);
cnt=0;
dfs(0);
vector<int> res;
if (cnt!=N)
{
if (cnt>=N-cnt) m=1;
else m=0;
for (int i=0; i<N; i++)
{
if (vs[i]&&m) res.push_back(i);
if (!vs[i]&&!m) res.push_back(i);
}
return res;
}
pair<int, int> mn={INT_MAX, 0};
for (int i=0; i<N; i++) mn=min(mn, {d[i].size(), i});
//cout<<"here "<<mn.first<<' '<<mn.second<<'\n';
if (mn.first>=((N-1)/2))
{
for (int i=0; i<N; i++) vs[i]=0;
int cur=mn.second;
while (1)
{
res.push_back(cur);
vs[cur]=1;
bool can=0;
for (auto v:d[u]) if (!vs[v]) can=1, cur=v;
if (!can) break;
}
return res;
}
else
{
for (int i=0; i<N; i++) if (!query(i, mn.second)&&i!=mn.second) res.push_back(i);
return res;
}
}
