#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

const int MX=305;

int memo[MX][MX];
int N;

bool ask(int i, int j) {
        if(i==j) return false;
        if(i>j) swap(i,j);
        if(memo[i][j]!=-1) return memo[i][j];
        return memo[i][j]=are_connected({i},{j});
}

bool vis[MX];

vector<vector<int>> comp;

void dfs(int v) {
        vis[v]=true;
        comp.back().push_back(v);
        for(int i=0;i<N;i++) {
                if(vis[i] || !ask(v,i)) continue;
                dfs(i);
        }
}

std::vector<int> longest_trip(int N, int D) {
        ::N=N;
        comp.clear();
        for(int i=0;i<N;i++) {
                vis[i]=false;
                for(int j=0;j<N;j++) {
                        memo[i][j]=-1;
                }
        }

        for(int i=0;i<N;i++) {
                if(vis[i]) continue;
                comp.push_back({});
                dfs(i);
        }

        if(comp.size()==1) {
                set<int> nodes;
                for(int i=0;i<N;i++) nodes.insert(i);

                vector<int> path;
                for(int i=0;i<N;i++) {
                
                        vector<int> adj;
                        for(int j=0;j<N;j++) {
                                if(ask(i,j)) adj.push_back(j);
                        }
                        if(adj.size()<2) continue;

                        int x=adj[0],y=adj[1];
                        nodes.erase(x);
                        nodes.erase(i);
                        nodes.erase(y);
                        path.push_back(x);
                        path.push_back(i);
                        path.push_back(y);        
                        break;
                }

                while(nodes.size()) {
                        int x=-1;
                        for(auto y:nodes) {
                                bool ok=0;
                                for(auto k:path) ok|=ask(k,y);
                                if(ok) {
                                        x=y;
                                        break;
                                }
                        }
                        nodes.erase(x);
                        assert(x!=-1);

                        if(ask(x,path.back())) {
                                path.push_back(x);
                                continue;
                        }

                        if(ask(x,path.front())) {
                                vector<int> nxt={x};
                                for(auto y:path) nxt.push_back(y);
                                path=nxt;
                                continue;
                        }

                        assert(ask(path.front(), path.back()));

                        for(int k=1;k<path.size();k++) {
                                if(ask(x,path[k])) {
                                        vector<int> nxt={x};
                                        for(int i=k;i<path.size();i++) {
                                                nxt.push_back(path[i]);
                                        }
                                        for(int i=0;i<k;i++) {
                                                nxt.push_back(path[i]);
                                        }
                                        path=nxt;
                                        break;
                                }
                        }
                }

                return path;
        } else {
                if(comp[0].size()>comp[1].size()) return comp[0];
                return comp[1];
        }
}