#include "island.h"
#include <set>
#include <queue>
#include <array>
#include <vector>

using namespace std;

const int MAXN = 200005;

int deg[MAXN];

queue <int> q;
set <int> e[MAXN];
vector < array <int, 2> > ans[2];

void add(int u, int v)
{
    ++ deg[u];
    ++ deg[v];
    e[u].insert(v);
    e[v].insert(u);
}

void construct_two_trees(int N, std::vector<int> U, std::vector<int> V)
{
    for(int i = 0; i < N; ++ i)
        add(i, (i + 1) % N);
    for(int i = 0; i < N - 3; ++ i)
        add(U[i], V[i]);

    for(int i = 0; i < N; ++ i)
    {
        if(deg[i] != 2)
            continue;
        int u = *e[i].begin(), v = *next(e[i].begin());
        add_vertex(i, u, v);
        add(i, N);
        add(u, N);
        add(v, N);
        ans[0].push_back({i, u});
        ans[0].push_back({i, v});
        ans[0].push_back({u, N});
        ans[1].push_back({u, v});
        ans[1].push_back({v, N});
        ans[1].push_back({i, N});
        break;
    }

    for(int i = 0; i <= N; ++ i)
        if(deg[i] == 2)
            q.push(i);
    while(!q.empty())
    {
        int u = q.front(), x = *e[u].begin(), y = *next(e[u].begin());
        q.pop();
        ans[0].push_back({u, x});
        ans[1].push_back({u, y});
        e[x].erase(u);
        e[y].erase(u);
        if(-- deg[x] == 2)
            q.push(x);
        if(-- deg[y] == 2)
            q.push(y);
    }
    report(ans[0]);
    report(ans[1]);
}