#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,a[MAXN],a1[MAXN],a2[MAXN],o[MAXN];
int qry(vector<int> a,vector<int> b)
{
    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);
}
int find(int u,int n,int a[])
{
    int l=1,r=n-1;vector<int> vc;
    while(l<=r)
    {
        vc.clear();for(int i=0;i<mid;++i) vc.pb(a[i]);
        if(qry({u},vc)) r=mid-1;else l=mid+1;
    }return a[r];
}
vector<int> longest_trip(int n,int type)
{
    vector<int> res;tp1=tp2=0;a1[tp1++]=0;
    iota(o,o+n,0);shuffle(o,o+n,rand1);
    for(int i=1,t,t1,t2;i<n;++i) if(tp2)
    {
        vector<int> vc;for(int j=0;j<tp1;++j) vc.pb(a1[j]);
        if(!qry({i},vc)) {a2[tp2++]=i;continue;}
        vc.clear();for(int j=0;j<tp2;++j) vc.pb(a2[j]);
        if(!qry({i},vc)) {a1[tp1++]=i;continue;}
        if(qry({i},{a1[0]})) t1=a1[0],t2=find(i,tp2,a2);
        else t1=find(i,tp1,a1),t2=a2[0];tp=0;
        for(int j=0;j<tp1;++j) if(t1!=a1[j]) a[tp++]=a1[j];
        a[tp++]=t1;a[tp++]=i;a[tp++]=t2;
        for(int j=0;j<tp2;++j) if(t2!=a2[j]) a[tp++]=a2[j];
        tp1=tp;tp2=0;copy(a,a+tp,a1);
    }
    else
    {
        if(qry({i},{a1[0],a1[tp1-1]}))
        {
            if(tp1<2 || qry({i},{a1[0]}))
            {for(int j=tp1;j;--j) a1[j]=a1[j-1];a1[0]=i;++tp1;}
            else a1[tp1++]=i;continue;
        }t=-1;for(int j=i-1;j>=0;--j) if(qry({i},{j})) {t=j;break;}
        if(t==-1) a2[tp2++]=i;
        else
        {
            tp=0;for(int j=0;j<tp1;++j) if(t==a1[j]) {t=j;break;}
            for(int j=t+1;j<tp1;++j) a[tp++]=a1[j];
            for(int j=0;j<=t;++j) a[tp++]=a1[j];a[tp++]=i;
            tp1=tp;copy(a,a+tp,a1);
        }
    }if(tp1<tp2) tp1=tp2,copy(a2,a2+tp2,a1);
    for(int i=0;i<tp1;++i) res.pb(o[a1[i]]);return res;
}