#include "longesttrip.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
typedef long long ll;
namespace{
struct DSU{
int n;
vector<int> dsu, sz;
DSU(int _n){
n = _n;
dsu.resize(n + 1);
sz.resize(n + 1);
for(int i = 1; i <= n; i++) dsu[i] = i, sz[i] = 1;
}
int query(int x){
if(dsu[x] == x) return dsu[x];
dsu[x] = query(dsu[x]);
return dsu[x];
}
void unite(int a, int b){
a = query(a);
b = query(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a, b);
dsu[b] = a;
sz[a] += sz[b];
}
};
}
std::vector<int> longest_trip(int n, int D){
DSU dsu(n);
vector<vector<int>> graph(n, vector<int>(n));
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
graph[i][j] = int(are_connected(vector<int>(1, i), vector<int>(1, j)));
graph[j][i] = graph[i][j];
if(graph[i][j]) dsu.unite(i, j);
}
}
if(dsu.sz[dsu.query(0)] < n){
int maxi = dsu.sz[dsu.query(0)], best = dsu.query(0);
for(int i = 0; i < n; i++){
if(i != dsu.query(i)) continue;
if(maxi < dsu.sz[i]){
best = i;
maxi = dsu.sz[i];
}
}
vector<int> ans;
for(int i = 0; i < n; i++){
if(dsu.query(i) == best) ans.push_back(i);
}
return ans;
}
vector<int> ans;
vector<int> ord;
for(int i = 0; i < n; i++) ord.push_back(i);
for(int i = 1; i < n; i++){
if(graph[0][i]){
swap(ord[1], ord[i]);
break;
}
}
ans.push_back(ord[0]);
ans.push_back(ord[1]);
bool flag = 1;
for(int i = 2; i < n; i++){
if(flag){
for(int j = i; j < n; j++){
bool f2 = 0;
for(int k = 0; k < i; k++){
if(graph[ans[k]][ord[j]]){
f2 = 1;
vector<int> nans;
for(int l = k + 1; l < i; l++) nans.push_back(ans[l]);
for(int l = 0; l <= k; l++) nans.push_back(ans[l]);
nans.push_back(ord[j]);
swap(ord[j], ord[i]);
ans = nans;
break;
}
}
if(f2){
break;
}
}
}
else{
vector<int> nans;
if(graph[ans[0]][ord[i]]){
nans.push_back(ord[i]);
for(auto &x: ans) nans.push_back(x);
ans = nans;
}
else{
ans.push_back(ord[i]);
}
}
if(graph[ans[0]][ans[i]]) flag = 1;
else flag = 0;
}
return ans;
}
