#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;
vector<vector<int>> adj;
/*
bool are_connected(vector<int> a, vector<int> b) {
cout << a[0] << ' ' << b[0] << endl;
int x;
cin >> x;
return (x == 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 (adj[v][i] == 1) {
dfs(i);
ok = 1;
break;
}
}
if (!ok) {
endik = v;
}
}
vector<int> dist, par;
void dfs_dist(int v, int d = 1, int p = -1) {
dist[v] = d;
par[v] = p;
used[v] = 1;
for (int i = 0; i < n; i++) {
if (used[i]) {
continue;
}
if (adj[v][i] == 1) {
dfs_dist(i, d + 1, v);
}
}
}
vector<int> longest_trip(int N, int d) {
n = N;
adj.assign(n, vector<int>(n, -1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (adj[i][j] == -1) {
if (are_connected({i}, {j})) {
adj[i][j] = 1;
adj[j][i] = 1;
} else {
adj[i][j] = 0;
adj[j][i] = 0;
}
}
}
}
for (int i = 0; i < n; i++) {
vector<int> notcon;
for (int j = 0; j < n; j++) {
if (adj[i][j] == 0) {
notcon.push_back(j);
}
}
if (notcon.size() >= n / 2) {
return notcon;
}
}
used.assign(n, 0);
dfs(0);
s.clear();
used.assign(n, 0);
dist.assign(n, inf);
par.assign(n, -1);
dfs_dist(endik);
int maxi = -1, mind = -1;
for (int i = 0; i < n; i++) {
if (dist[i] > maxi) {
maxi = dist[i];
mind = i;
}
}
while (mind != -1) {
s.push_back(mind);
mind = par[mind];
}
return s;
}
/*
signed main() {
int N, D;
cin >> N >> D;
auto res = longest_trip(N, D);
for (auto el : res) {
cout << el << ' ';
}
cout << endl;
}
*/
