#include "island.h"
#include<bits/stdc++.h>
using namespace std;
int n;
namespace sub1246{
void solve(){
vector<bool>vis(n + 1, false);
vis[1] = true;
for(int d = 1; d < n; d++){
int x = query(1, d);
for(int i = 1; true; i++){
int y = query(x, i);
if(vis[y]){
answer(x, y);
break;
}
}
vis[x] = true;
}
}
}
namespace sub3578{
void solve(){
vector<bool>vis(n + 1, false);
vis[1] = true;
for(int d = 1; d < n; d++){
int x = query(1, d);
if(!vis[x]){
for(int i = 1; true; i++){
int y = query(x, i);
answer(x, y);
if(vis[y]){
break;
}
vis[y] = true;
}
vis[x] = true;
}
}
}
}
void solve(int N, int L){
n = N;
if(L == n * n){
sub1246::solve();
}
else{
sub3578::solve();
}
}
