#include<bits/stdc++.h>
#include "longesttrip.h"
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
// #define int ll
// #define N 
using namespace std;
std::vector<int> longest_trip(int n, int D)
{
    poly rt;
    rt.push_back(0);
    poly vis(n,0);
    for (int i=1;i<n;i++)
        if (are_connected((poly){0},(poly){i}))
        {
            rt.push_back(i);
            vis[i]=1;
            break;
        }
    poly lf;
    lf.push_back(0);
    for (int i=1;i<n;i++)
        if (!vis[i])
        {
            if (are_connected((poly){lf.back()},(poly){i}))
            {
                lf.push_back(i);
            } else rt.push_back(i);
        }
    poly ans;
    while (lf.size()>1) ans.push_back(lf.back()),lf.pop_back();
    for (auto u:rt) ans.push_back(u);
    return ans;
}