#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) {
                for(int i=0;i<N;i++) {
                        vector<int> nxt;
                        for(int j=0;j<N;j++) {
                                if(ask(i,j)) nxt.push_back(j);
                        }

                        if(nxt.size()==1) {
                                vector<int> res;
                                res.push_back(i);
                                res.push_back(nxt[0]);

                                for(int j=0;j<N;j++) {
                                        if(j!=i && j!=nxt[0] && ask(nxt[0],j)) {
                                                res.push_back(j);
                                                break;
                                        }
                                }

                                for(int j=0;j<N;j++) {
                                        if(j!=res[0] && j!=res[1] && j!=res[2]) {
                                                res.push_back(j);
                                        }
                                }
                                return res;
                        }
                }

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