#include "island.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
//query
//answer
struct DSU{
vector<int>e;
void init(int n){
e=vector<int>(n,-1);
}
int get(int x){
return e[x]<0?x:e[x]=get(e[x]);
}
bool unite(int x, int y){
x=get(x); y=get(y);
if(x==y) return 0;
if(e[x]>e[y]) swap(x,y);
e[x]+=e[y];
e[y]=x;
return 1;
}
};
void solve(int n, int l){
int ptr[n+5];
memset(ptr,0,sizeof(ptr));
set<int>se[n+5];
int val[n+5];
for(int x=1;x<=n;x++){
ptr[x]=1;
val[x]=query(x,ptr[x]);
}
DSU dsu;
dsu.init(n+5);
for(int x=0;x<n-1;x++){
for(int y=1;y<=n;y++){
if(val[y]==-1) continue;
if(val[val[y]]==-1) continue;
if(y==val[val[y]]){
int nxt=val[y];
answer(y,nxt);
dsu.unite(y,nxt);
se[y].insert(nxt);
se[nxt].insert(y);
ptr[y]++;
ptr[nxt]++;
while(1){
val[nxt]=query(nxt,ptr[nxt]);
if(se[nxt].find(val[nxt])==se[nxt].end()) break;
ptr[nxt]++;
}
while(1){
val[y]=query(y,ptr[y]);
if(se[y].find(val[y])==se[y].end()) break;
ptr[y]++;
}
break;
}
}
//check
for(int y=1;y<=n;y++){
if(val[y]==-1) continue;
if(dsu.get(y)==dsu.get(val[y])){
val[y]=-1;
}
}
}
}
