#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
ll inf = 1e18;
vector<int> s;
vector<int> used;
int n;
int endik = -1;
void dfs(int v) {
s.push_back(v);
used[v] = 1;
bool ok = 0;
for (int i = 0; i < n; i++) {
if (used[i]) {
continue;
}
if (are_connected({v}, {i})) {
dfs(i);
ok = 1;
break;
}
}
if (!ok) {
endik = v;
}
}
vector<int> longest_trip(int N, int d) {
n = N;
used.assign(n, 0);
dfs(0);
used.assign(n, 0);
dfs(endik);
return s;
}
