#include "island.h"
#include<bits/stdc++.h>
#define reg register
const int N=1e5+10;
int vis[N],d[N];
std::vector<int> G[N];
std::vector<std::array<int,2>> T1,T2;
std::map<std::pair<int,int>,bool> mp;
inline void add(reg int u,reg int v){G[u].push_back(v),G[v].push_back(u),d[u]++,d[v]++;}
void construct_two_trees(int n, std::vector<int> U, std::vector<int> V){
    for (reg int i=0;i<n-3;i++) mp[{U[i],V[i]}]=1,add(U[i],V[i]);
    for (reg int i=0;i<n;i++) add(i,(i+1)%n),mp[{i,(i+1)%n}]=1;
    reg int A,B,C; std::queue<int> q;
    for (reg int i=0;i<n;i++){
        reg int a=i,b=(i+1)%n,c=(i+2)%n;
        if (mp.count({a,c})||mp.count({c,a})){
            A=a,B=b,C=c,add_vertex(a,b,c);
            add(a,n),add(b,n),add(c,n);
            break;
        }
    }
    // std::cerr<<A<<" "<<B<<" "<<C<<"\n";
    for (reg int i=0;i<=n;i++) if (d[i]==2) q.push(i);
    while (!q.empty()){
        reg int u=q.front(),x=-1,y=-1; vis[u]=1,q.pop();
        // std::cerr<<"<< "<<u<<"\n";
        for (auto v:G[u]) if (!vis[v]) x>-1?y=v:x=v;
        assert(x>-1&&y>-1);
        if ((--d[x])==2) q.push(x); T1.push_back({u,x});
        if ((--d[y])==2) q.push(y); T2.push_back({u,y});  
    }
    T1.push_back({A,B}),T1.push_back({A,C}),T1.push_back({B,n});
    T2.push_back({B,C}),T2.push_back({A,n}),T2.push_back({C,n});
    report(T1),report(T2);
}