#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=305;
int qrs[nx][nx], vs[nx], m, cnt, u, v, r[nx], st, ed, p;
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;
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;
}
st=ed=0;
queue<pair<int, int>> q;
q.push({0, 0});
for (int i=0; i<N;i ++) vs[i]=0;
vs[0]=1;
while (!q.empty())
{
auto [u, p]=q.front();
if (u!=0)
{
if (query(u, st)) r[u]=st, st=u;
else if (query(u, ed)) r[ed]=u, ed=u;
else
{
r[ed]=st;
r[u]=p;
st=u;
}
}
q.pop();
for (auto v:d[u])
{
if (!vs[v]) vs[v]=1, q.push({v, u});
}
}
while (st!=ed) res.push_back(st), st=r[st];
res.push_back(ed);
return res;
}
