#include "gra.h"
#define N 1005
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)
int f1[N],f2[N],cnt1,cnt2;
int fd1(int x){return x^f1[x]?f1[x]=fd1(f1[x]):x;}
int fd2(int x){return x^f2[x]?f2[x]=fd2(f2[x]):x;}
void mg1(int x,int y){f1[fd1(x)]=y;}
void mg2(int x,int y){f2[fd2(x)]=y;}
struct edge{int u,v;}e1[N],e2[N];
void tree(int n) {
    fo(i,1,n)f1[i]=f2[i]=i;
    fo(i,2,n){
        bool c=query(i,i-1);
        if(!c)f1[i]=i-1,e1[++cnt1]={i,i-1};
        else f2[i]=i-1,e2[++cnt2]={i,i-1};
        int now;
        if(fd1(i-1)==1)now=fd2(i)-1;
        else now=fd1(i)-1;
        while(fd1(i)!=1&&fd2(i)!=1){
            c=query(now,i);
            if(!c)f1[fd1(i)]=now,e1[++cnt1]={now,i},now=fd1(now)-1;
            else f2[fd2(i)]=now,e2[++cnt2]={now,i},now=fd2(now)-1;
        }
    }
    if(fd1(n)==1)
        fo(i,1,cnt1)
            report(e1[i].u,e1[i].v);
    else
        fo(i,1,cnt2)
            report(e2[i].u,e2[i].v);
}