#include <iostream>
#include <complex>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
#include <cstdint>
#include <cassert>
#include "longesttrip.h"
using namespace std;
vector <int> longest_trip(int n, int d)
{
vector <vector<int>> v(n, vector <int> ()),
s(n, vector <int> (n, -1));
auto add = [&] (int a, int b) -> void {
if(s[a][b] == -1){
s[a][b] = s[b][a] = 1;
v[a].push_back(b);
v[b].push_back(a);
}
};
if(d == 3){
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++) {
add(i, j);
}
}
}else if(d == 2){
for(int i = 0; i < n; i++)
{
for(int j = i+1; j < n; j++)
{
if(s[i][j] == -1){
s[i][j] = are_connected({ i }, { j });
if(s[i][j] == 0){
for(int k = 0; k < n; k++){
add(i, k); add(j, k);
}
}else{
s[i][j] = -1; add(i, j);
}
}
}
}
} else if(d == 1){
for(int i = 0; i < n; i++)
{
for(int j = i+1; j < n; j++)
{
if(s[i][j] == -1){
s[i][j] = are_connected({ i }, { j });
if(s[i][j] == 1) {
s[i][j] = -1;
add(i, j);
}
}
}
}
}
vector <int> pass(n), ans, path;
auto dfs = [&] (auto dfs, int node, int parent) -> void
{
path.push_back(node); pass[node] = 1;
if(path.size() > ans.size()) ans = path;
for(auto& u : v[node]) if(!pass[u])
{
dfs(dfs, u, node);
}
path.pop_back();
};
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++){
pass[j] = 0;
}
dfs(dfs, i, i);
}
return ans;
}
