#include <bits/stdc++.h>
#include "island.h"
using namespace std;
void solve(int n,int l){
int x,x1,x2;
map<pair<int,int>,int>di;
vector<int>d(n+1),cn(n+1),vi(n+1),a;
d[1]=1;
a.push_back(1);
x=query(1,1);
cn[1]++;
d[x]=1;
di[{1,x}]=1;
di[{x,1}]=1;
answer(1,x);
a.push_back(x);
x1=query(x,1);
cn[x]++;
if (x1!=1){
a.push_back(x1);
d[x1]=1;
answer(x,x1);
cn[x]++;
di[{x,x1}]=1;
di[{x1,x}]=1;
}
else{
x1=query(1,2);
x2=query(x,2);
if (x1!=x2){
a.push_back(x1);
d[x1]=1;
answer(1,x1);
cn[1]++;
di[{1,x1}]=1;
di[{x1,1}]=1;
a.push_back(x2);
d[x2]=1;
answer(x,x2);
cn[x]++;
di[{x,x2}]=1;
di[{x2,x}]=1;
}
else{
int p;
int i=1;
while (((p=query(x1,i))!=1) and (p!=x)){
i++;
}
a.push_back(x1);
d[x1]=1;
answer(p,x1);
cn[p]++;
di[{p,x1}]=1;
di[{x1,p}]=1;
}
}
int c=a.size();
while (c<n){
int h=a.back();
x=query(h,cn[h]+1);
cn[h]++;
if (di[{x,h}])continue;
if (d[x]){
a.pop_back();
continue;
}
a.push_back(x);
d[x]=1;
answer(h,x);
di[{h,x}]=1;
di[{x,h}]=1;
c++;
}
return;
}
