#pragma GCC optimize("Ofast","unroll-all-loops")
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int N,int D){
vector<vector<int>> adj(N);
vector areConnected(N,vector<bool>(N));
for(int i=0;i<N;i++) {
for(int j=i+1;j<N;j++) {
if(are_connected({i},{j})) {
adj[i].emplace_back(j);
adj[j].emplace_back(i);
areConnected[i][j]=areConnected[j][i]=true;
}
}
}
{
// Case 1 if two components
int isTwo = -1;
{
vector<bool> visited(N);
int curr = 0;
function<void(int)> dfs = [&](int x) {
if(visited[x])return;
visited[x]=true;
curr++;
for(int&i:adj[x])dfs(i);
};
dfs(0);
if(curr!=N) {
if(curr>=N-curr)isTwo=curr;
else {
for(int i=0;i<N;i++) {
if(!visited[i]){
isTwo=i;break;
}
}
}
}
}
if(isTwo!=-1) {
vector<bool> visited(N);
vector<int> ans;
function<void(int)> dfs = [&](int x) {
visited[x]=true;
ans.emplace_back(x);
for(int&i:adj[x])if(!visited[i]) {
dfs(i);
return;
}
};
dfs(isTwo);
return ans;
}
}
vector<vector<int>> path(3);
vector<bool> visited(N);
function<int(int,int)> dfs = [&](int x,int def) {
visited[x]=true;
int state = def;
int children = 0;
for(int&i:adj[x])if(!visited[i]) {
children++;
if(children==2) {
assert(dfs(i,2)==2);
state=0;
break;
}
auto ans = dfs(i,def);
if(ans==0) {
state = 0;
break;
}
}
path[state].emplace_back(x);
return state;
};
auto curr = dfs(0,1);
if(curr==1) {
return path[1];
}
assert(curr==0);
if(path[0].size()==1) {
vector<int> ans = path[1];
ans.emplace_back(path[0][0]);
reverse(path[2].begin(),path[2].end());
for(int&i:path[2])ans.emplace_back(i);
return ans;
}
if(!areConnected[path[0][1]][path[1][0]])swap(path[1],path[2]);
path[1].emplace_back(path[0][0]);
path[0].erase(path[0].begin());
reverse(path[0].begin(),path[0].end());
reverse(path[2].begin(),path[2].end());
auto ans = path[0];
for(int&i:path[1])ans.emplace_back(i);
for(int&i:path[2])ans.emplace_back(i);
return ans;
}
