#include "island.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 12;
set<int> g[maxn];
int s[maxn];
void add(int x,int y){
    // cout << x << ' ' << y << '\n';
    s[x]++;
    s[y]++;
    g[x].insert(y);
    g[y].insert(x);
}
void construct_two_trees(int N, std::vector<int> U, std::vector<int> V){
    set<pair<int,int>> deg;
    for(int i = 1;i < N;i++){
        add(i,i-1);
    }
    add(0,N-1);
    for(int i = 0;i < N - 3;i++){
        add(U[i],V[i]);
        int x = min(V[i],U[i]),y = max(V[i],U[i]);
        if(y - x == 2){
            int d = add_vertex(x,y,y-1);
            add(d,x);
            add(d,y);
            add(d,y-1);
            break;
        }else if((x == 0 && y == N - 2) || (x == 1 && y == N - 1)){
            int z;
            if(!x){
                z = y + 1;
            }else{
                z = x - 1;
            }
            int d = add_vertex(x,y,z);
            add(d,x);
            add(d,y);
            add(d,z);
            break;
        }
    }
    if(N == 3){
        int d = add_vertex(0,1,2);
        add(d,0);add(d,1);add(d,2);
    }
    N++;
    for(int i = 0;i < N;i++){
        deg.insert({s[i],i});
    }
    vector<array<int,2>> t,t1;
    while(deg.size()){
        auto [col,v] = (*deg.begin());
        if(col != 2) break;
        deg.erase(deg.begin());
        int x = (*g[v].begin()),y = (*g[v].rbegin());
        auto del = [&](int e,int f){
            deg.erase({s[f],f});
            s[f]--;
            g[f].erase(e);
            deg.insert({s[f],f});
        };
        t.push_back({v,x});
        t1.push_back({v,y});
        del(v,x);
        del(v,y);
    }
    // assert((int)deg.size() == 4);
    vector<array<int,2>> edges;
    for(auto [d,v]:deg){
        for(auto [d1,v1]:deg){
            if(v1 > v){
                // cout << v << ' ' << v1 << '\n';
                edges.push_back({v,v1});
            }
        }
    }
    t.push_back(edges[0]);
    t.push_back(edges[1]);
    t1.push_back(edges[5]);
    t1.push_back(edges[2]);
    t1.push_back(edges[3]);
    t.push_back(edges[4]);
    // assert((int)t.size() == (int)t1.size());
    report(t);
    report(t1);
}