#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int N, int D){
if(D==3){
vector<int> tt;
for(int i = 0;i<N;i++)tt.push_back(i);
return tt;
}
if(D==2){
int cur=0;
vector<int> res = {cur};
set<int> left;
for(int i = 1;i<N;i++)left.insert(i);
for(int i=0;i<N-2;i++){
int f=*(left.begin());
int s=*(++left.begin());
if(are_connected({cur}, {f})){
left.erase(f);
res.push_back(f);
cur=f;
}
else{
left.erase(s);
res.push_back(s);
cur=s;
}
}
auto last=*(left.begin());
if(are_connected({res.back()},{last})){
res.push_back(last);
return res;
}
else{
auto t1=res.back();
res.pop_back();
auto t2=res.back();
res.pop_back();
res.push_back(t1);
res.push_back(t2);
res.push_back(last);
return res;
}
}
//finished special cases
/*
could get 40 more points with smth trivial
cuz D=1 at least
so finding longest path is easier i think
oh ok algo for tc3 trivial
*/
vector<int> cur={0};
int wt=(N+1)/2;
set<int> left;
for(int i = 1;i<N;i++)left.insert(i);
while(cur.size()<wt){
auto top=cur.back();
vector<int> nc;
int ss=-1;
for(int i = 0;i<N;i++){
if(i==top)continue;
if(are_connected({top}, {i})){
if(left.count(i))ss=i;
}
else{
nc.push_back(i);
}
}
if(nc.size()>=wt){
return nc;
}
cur.push_back(ss);
left.erase(ss);
}
return cur;
}
