#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long
#define ff first
#define ss second
#define vi vector<int>
const int N = 200005;
std::vector<int> longest_trip(int n, int D)
{
if(D == 3){
vector<int> v;
for(int i = 0; i < n; ++i) v.pb(i);
return v;
}
if(D == 2){
deque<int> v;
v.pb(0);
int o = -1;
for(int i = 1; i < n; ++i){
bool x = are_connected(vi{0}, vi{i});
if(x){
o = i;
v.pb(i);
break;
}
}
if(o == -1){
vi res;
for(int i = 1; i < n; ++i){
res.pb(i);
}
return res;
}
for(int i = 1; i < n; ++i){
if(o == i) continue;
bool x = are_connected(vi{v[0]}, vi{i});
if(x){
v.push_front(i);
}else v.pb(i);
}
vector<int> res(all(v));
return res;
}
vector<vector<int>> g(n);
vector<vector<bool>> is(n, vector<bool>(n));
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
bool ok = are_connected(vi{i}, vi{j});
if(ok){
is[i][j] = is[j][i] = 1;
g[i].pb(j);
g[j].pb(i);
}
}
}
vector<vector<int>> S;
for(int i = 0; i < n; ++i){
if(g[i].empty()){
vi res;
for(int j = 0; j < n; ++j){
if(j != i) res.pb(j);
}
return res;
}
bool okk = 0;
for(auto &s: S){
bool ok = 1;
for(int x: s){
if(is[x][i] == 0) ok = 0;
}
if(ok == 1){
s.pb(i);
okk = 1;
break;
}
}
if(okk == 0){
S.pb(vi{i});
}
}
if(S.size() == 2){
for(int &x: S[0]){
for(int &y: S[1]){
if(is[x][y]){
swap(x, S[0].back());
swap(y, S[1][0]);
vi res;
for(int f: S[0]) res.pb(f);
for(int f: S[1]) res.pb(f);
return res;
}
}
}
if(S[0].size() > S[1].size()) return S[0];
return S[1];
}
vi res;
for(auto v: S){
for(int x: v) res.pb(x);
}
return res;
}
