#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
#define pb push_back
#define mid ((l+r)/2)
const int MAXN=305;mt19937 rand1(0);
int tp,tp1,tp2,cnt,a[MAXN],a1[MAXN],a2[MAXN],o[MAXN],z[MAXN];
int qry(vector<int> a,vector<int> b)
{
    ++cnt;
    sort(a.begin(),a.end());sort(b.begin(),b.end());
    a.resize(unique(a.begin(),a.end())-a.begin());
    b.resize(unique(b.begin(),b.end())-b.begin());
    for(auto &i:a) i=o[i];for(auto &i:b) i=o[i];
    return are_connected(a,b);
}
pair<int,int> find(vector<int> a,vector<int> b)
{
    if(a.size()<b.size()) swap(a,b);
    if(a.size()<2) return {a[0],b[0]};int t=a.size()/2;
    vector<int> a1(a.begin(),a.begin()+t),a2(a.begin()+t,a.end());
    if(qry(a1,b)) return find(a1,b);return find(a2,b);
}
vector<int> longest_trip(int n,int type)
{
    vector<int> res;tp1=tp2=0;a1[tp1++]=0;fill(z,z+n,-1);
    iota(o,o+n,0);shuffle(o,o+n,rand1);
    for(int i=1,t;i<n;) if(tp2)
    {
        if(a1[tp1-1]>a2[tp2-1]) swap(tp1,tp2),swap(a1,a2);
        t=-1;for(int j=i;j<n;++j) if(qry({j},{a1[tp1-1]})) {t=j;break;}
        if(t==-1) {for(int j=i;j<n;++j) a2[tp2++]=j;break;}
        a1[tp1++]=t;for(int j=i;j<t;++j) a2[tp2++]=j;
        if(qry({t},{t-1}))
            reverse(a2,a2+tp2),copy(a2,a2+tp2,a1+tp1),tp1+=tp2,tp2=0;i=t+1;
    }
    else
    {
        t=-1;for(int j=i;j<n;++j) if(qry({j},{a1[tp1-1]})) {t=j;break;}
        if(t==-1) {for(int j=i;j<n;++j) a2[tp2++]=j;break;}
        a1[tp1++]=t;for(int j=i;j<t;++j) a2[tp2++]=j;
        if(t>i && qry({t},{t-1}))
            reverse(a2,a2+tp2),copy(a2,a2+tp2,a1+tp1),tp1+=tp2,tp2=0;i=t+1;
    }
    if(tp2)
    {
        if(qry({a1[0],a1[tp1-1]},{a2[0],a2[tp2-1]}))
        {
            if(qry({a1[0]},{a2[0]}))
            {
                reverse(a1,a1+tp1);
                copy(a2,a2+tp2,a1+tp1);tp1+=tp2;tp2=0;
            }
            else if(qry({a1[0]},{a2[tp2-1]}))
                copy(a1,a1+tp1,a2+tp2),tp2+=tp1,tp1=0;
            else if(qry({a1[tp1-1]},{a2[0]}))
                copy(a2,a2+tp2,a1+tp1),tp1+=tp2,tp2=0;
            else
            {
                reverse(a1,a1+tp1);
                copy(a1,a1+tp1,a2+tp2);tp2+=tp1;tp1=0;
            }
        }
        else
        {
            vector<int> vc1(a1,a1+tp1),vc2(a2,a2+tp2);
            if(qry(vc1,vc2))
            {
                auto [u1,u2]=find(vc1,vc2);int t1=-1,t2=-1;tp=0;
                for(int i=0;i<tp1;++i) if(u1==a1[i] || u2==a1[i]) {t1=i;break;}
                for(int i=0;i<tp2;++i) if(u1==a2[i] || u2==a2[i]) {t2=i;break;}
                for(int i=t1+1;i<tp1;++i) a[tp++]=a1[i];
                for(int i=0;i<=t1;++i) a[tp++]=a1[i];
                for(int i=t2;i<tp2;++i) a[tp++]=a2[i];
                for(int i=0;i<t2;++i) a[tp++]=a2[i];
                tp1=tp;tp2=0;copy(a,a+tp,a1);
            }
        }
    }if(tp1<tp2) swap(tp1,tp2),swap(a1,a2);
    for(int i=0;i<tp1;++i) res.pb(o[a1[i]]);assert(cnt<=409);return res;
}