#include "longesttrip.h"
#include<bits/stdc++.h>
#define int long long
#define f0r(i,n) for(int i = 0;i<n;i++)
#define FOR(i, k, n) for(int i = k;i<n;i++)
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define mp make_pair
#define vpii vector<pii>
#define vvi vector<vi>
#define vb vector<bool>
using namespace std;
const int mxn = 260;
vvi adj(mxn);
std::vector<signed> longest_trip(signed N, signed D)
{
f0r(i, N){
adj[i].clear();
}
vector<vector<bool>> con(N, vector<bool>(N, false));
f0r(i, N){
FOR(j, i+1, N){
con[i][j] = are_connected({i}, {j});
con[j][i] = con[i][j];
if(con[i][j]){
adj[i].pb(j); adj[j].pb(i);
}
}
}
f0r(i, N)con[i][i] = 1;
int sum = 0;
f0r(i,N){
f0r(j,N){
sum += con[i][j];
}
}
vector<signed>ans;
if(sum == N * N){
f0r(i,N)ans.pb(i);
return ans;
}
vector<vector<signed>> ccs;
vb vis(N);
f0r(i, N){
if(!vis[i]){
vector<signed> curcc;
queue<int>q;
q.push(i); vis[i]=1; curcc.pb(i);
while(!q.empty()){
int node = q.front(); q.pop();
for(auto u : adj[node]){
if(vis[u])continue;
vis[u] = 1; q.push(u); curcc.pb(u);
}
}
ccs.pb(curcc);
}
}
if(ccs.size() > 1){
int mx = 0; int mxd = 0;
f0r(i,ccs.size()){
if(ccs[i].size() > mx){
mx = ccs[i].size(); mxd = i;
}
}
for(auto u : ccs[mxd])ans.pb(u);
return ans;
}
else{
int a,b,c;
f0r(i, N){
f0r(j, N){
f0r(k, N){
if(i != j && i != k && j != k && con[i][j] && con[j][k] && !con[i][k]){
a=i; b=j; c=k;
}
}
}
}
deque<signed>tmp;
tmp.pb(a); tmp.pb(b); tmp.pb(c);
vb vis(N);
vis[a] = 1; vis[b] = 1; vis[c] = 1;
// cout<<a<<' '<<b<<' '<<c<<'\n';
int cnt = 3;
while(cnt < N){
if(cnt == N-1){
int nxt = 0;
f0r(i, N){
if(!vis[i])nxt = i;
}
if(con[tmp.back()][nxt])tmp.pb(nxt);
else tmp.push_front(nxt);
cnt++;
break;
}
else{
int l = tmp.front(); int r = tmp.back();
bool ok = 0;
f0r(i,N){
if(!vis[i]){
if(con[l][i] && !con[r][i]){
ok = 1; tmp.push_front(i); vis[i] = 1; cnt++; break;
}
else if(con[r][i] && !con[l][i]){
ok = 1; tmp.pb(i); vis[i] = 1; cnt++; break;
}
}
}
if(!ok){
f0r(i,N){
f0r(j, N){
if(i != j && !vis[i] && !vis[j] && !con[i][j]){
vis[i] = 1; vis[j] = 1; cnt+=2;
tmp.push_front(i); tmp.pb(j); ok = 1; break;
}
}
if(ok)break;
}
if(!ok){
f0r(i, N){
if(!vis[i]){
tmp.pb(i);
}
}
cnt = N;
}
}
}
}
while(!tmp.empty()){
ans.pb(tmp.front()); tmp.pop_front();
}
return ans;
}
}
