#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(1); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

vector<int> longest_trip(int n, int D) {
    VI ch;
    vector<set<int>> notc(n);
    VI ord(n);
    iota(all(ord),0);
    shuffle(all(ord),mrand);
    vector<vector<int>> g(n,VI(n,-1));
    auto addupd=[&](int x,int y) {
        if (notc[x].count(y)) return;
        for (auto z:notc[x]) g[z][y]=g[y][z]=1;
        g[x][y]=0;
        notc[x].insert(y);
    };
    auto query=[&](int u,int v) {
        assert(u!=v);
        if (g[u][v]!=-1) return g[u][v];
        bool w=are_connected(VI{u},VI{v});
        if (!w) {
            addupd(u,v); addupd(v,u);
        }
        return g[u][v]=g[v][u]=w;
    };
    auto querypat=[&](int u,VI pat) {
        assert(!pat.empty());
        for (auto v:pat) {
            assert(u!=v);
            if (g[u][v]==1) return v;
        }
        rep(i,0,SZ(pat)) rep(j,i+1,SZ(pat)) {
            int v1=pat[i],v2=pat[j];
            if (g[v1][v2]==0) return query(u,v1)?v1:v2;
        }
        VI unk;
        for (auto v:pat) if (g[u][v]==-1) unk.pb(v);
        if (SZ(unk)==0) return -1;
        int l=0,r=SZ(unk)+1;
        while (l+1<r) {
            int md=(l+r)>>1;
            VI w(unk.begin(),unk.begin()+md);
            if (are_connected(VI{u},w)) r=md; else {
                for (auto v:w) addupd(u,v),addupd(v,u);
                l=md;
            }
        }
        if (l==SZ(unk)) return -1;
        else return unk[l];
    };
    VI unv;
    VI q1,q2;
    bool con=query(ord[0],ord[1]);
    if (con) ch=VI{ord[0],ord[1]};
    else {
        q1=VI{ord[0]};
        q2=VI{ord[1]};
    }
    unv=VI(ord.begin()+2,ord.end());
    for (auto w:unv) {
        if (!con) {
            if (rnd(SZ(q1)+SZ(q2))>=SZ(q2)) swap(q1,q2);
            if (!are_connected({w},q1)) {
                for (auto v:q1) addupd(w,v),addupd(v,w);
                q2.pb(w);
            } else {
                if (!are_connected({w},q2)) {
                    for (auto v:q2) addupd(v,w),addupd(w,v);
                    q1.pb(w);
                } else {
                    query(w,q1[0]); query(w,q2[0]);
                    int u1=querypat(w,q1);
                    int u2=querypat(w,q2);
                    assert(u1!=-1&&u2!=-1);
                    q1.erase(find(all(q1),u1)); q1.pb(u1);
                    q2.erase(find(all(q2),u2));
                    ch=q1; ch.pb(w); ch.pb(u2);
                    for (auto v:q2) ch.pb(v);
                    con=1;
                }
            }
        } else {
            if (rnd(2)) reverse(all(ch));
            int u=ch[0],v=ch[SZ(ch)-1];
            if (query(v,w)) {
                ch.pb(w); continue;
            } else if (query(u,w)) {
                ch.insert(ch.begin(),w); continue;
            } else {
                int md=querypat(w,ch);
                if (md!=-1) {
                    rotate(ch.begin(),find(all(ch),md),ch.end());
                    ch.insert(ch.begin(),w);
                } else {
                    con=0;
                    q1=ch;
                    q2=VI{w};
                }
            }
        }
    }
    if (con) return ch;
    else {
        if (SZ(q1)<SZ(q2)) swap(q1,q2);
        return q1;
    }
}