#include "longesttrip.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <tuple>
#include <queue>
#include <bitset>
#define ff first
#define ss second
using namespace std;
struct DisjointSetUnion {
int n;
vector<int> fa;
DisjointSetUnion(int _n) : n(_n), fa(n) {iota(fa.begin(), fa.end(), 0);}
};
bool are_connected(std::vector<int> A, std::vector<int> B);
std::vector<int> longest_trip(int N, int D) {
int n = N;
if (D == 3) {
vector<int> p(n);
iota(p.begin(), p.end(), 0);
return p;
}
if (D == 2) {
vector<bool> vis(n);
vector<int> a, b;
if (are_connected({0}, {1})) {
a.push_back(0);
b.push_back(1);
vis[0] = vis[1] = 1;
}else{
a.push_back(0);
b.push_back(2);
vis[0] = vis[2] = 1;
}
for (int i=0; i<n; i++) {
if (vis[i]) continue;
vis[i] = true;
are_connected({i}, {a.back()}) ? a.push_back(i) : b.push_back(i);
}
vector<int> ans;
ans.insert(ans.end(), a.rbegin(), a.rend());
ans.insert(ans.end(), b.begin(), b.end());
return ans;
}
vector<vector<int>> adj(n);
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
if (are_connected({i}, {j})) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
vector<int> ans;
for (int i=0; i<n; i++) {
vector<bool> vis(n);
vector<int> stk;
vector<int> deg(n);
for (int i=0; i<n; i++) deg[i] = adj[i].size();
int u = i;
while (true) {
vis[u] = true;
stk.push_back(u);
pair<int, int> best = {n, n};
for (int v: adj[u]) {
if (vis[v]) continue;
best = min(best, pair<int, int>{--deg[v], v});
}
if (best.second == n) break;
u = best.second;
}
if (stk.size() > ans.size()) ans = stk;
}
return ans;
}
