#include "longesttrip.h"
#include <bits/stdc++.h>
#include <iterator>
using namespace std;
std::vector<int> longest_trip(int n, int D)
{
vector<vector<bool>> mt(n, vector<bool>(n));
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})){
mt[i][j] = 1;
mt[j][i] = 1;
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
// D = 1 :D
//vedo se ci sono due cc (ez dfs)
// poi devo togliere questo pezzo
vector<bool> vis(n, 0);
function<void(int)> dfs = [&](int v){
vis[v] = 1;
for(int u: adj[v]){
if(vis[u]) continue;
dfs(u);
}
};
dfs(0);
int cnt = 0;
for(int i = 0; i<n; i++) cnt += vis[i];
if(cnt != n){
vector<int> sol;
if(cnt >= (n+1)/2){
for(int i= 0; i<n; i++) if(vis[i]) sol.push_back(i);
}
else{
for(int i= 0; i<n; i++) if(!vis[i]) sol.push_back(i);
}
return sol;
}
//trovo due non collegati
vector<int> first;
vector<int> second;
for(int i = 0; i<n; i++){
for(int j = i+1; j<n; j++){
if(!mt[i][j]){
first.push_back(i);
second.push_back(j);
i = n; break;
}
}
}
if(first.empty()){
vector<int> sol(n);
iota(sol.begin(), sol.end(), 0);
return sol;
}
//ciclo sugli altri e dvido in tre array
vector<int> md;
for(int i = 0; i<n; i++){
if(i == first[0] || i == second[0]) continue;
bool b1 = mt[i][first[0]];
bool b2 = mt[i][second[0]];
if(b1 && b2) md.push_back(i);
else if(b1) first.push_back(i);
else if(b2) second.push_back(i);
else assert(0);
}
//separo a metà quelli in mezzzo
if(md.size()){
vector<int> md1 = {md[0]};
vector<int> md2;
for(int i = 1; i<md.size(); i++){
if(mt[md[0]][i]) md1.push_back(i);
else md2.push_back(i);
}
//assegno le due metà
for(int i: first){
if(!mt[i][md1[0]]){
swap(md1, md2);
break;
}
}
for(int i: md1) first.push_back(i);
for(int i: md2) second.push_back(i);
}
//visito cricca sx a partire da uno in mezzo e visito cricca dx allo stesso modo
for(int i: first){
for(int j: second){
if(mt[i][j]){
vector<int> sol;
for(int i_:first){
if(i_ == i) continue;
sol.push_back(i_);
}
sol.push_back(i);
sol.push_back(j);
for(int i_:second){
if(i_==j) continue;
sol.push_back(i_);
}
return sol;
}
}
}
assert(0);
}
