#include<bits/stdc++.h>
#include "island.h"
#define rep(i,l,r) for (int i(l), i##end(r); i <= i##end; ++i)
#define per(i,r,l) for (int i(r), i##end(l); i >= i##end; --i)
#define LL long long
#define eb emplace_back
using namespace std;
#define edge array <int, 2>

const int Maxn = 2e5 + 9;
int n;
int deg[Maxn], vis[Maxn];
vector <edge> tree1, tree2;
vector <int> G[Maxn];

queue <int> que;
set <int> Sa;

void construct_two_trees(int N, std::vector<int> U, std::vector<int> V) {
    n = N;
    rep (i, 0, n - 4) {
        int u, v; u = U[i], v = V[i];
        G[u].eb(v), G[v].eb(u);
    }
    rep (u, 0, n - 1) {
        int v = u + 1; if (v == n) v = 0;
        G[u].eb(v), G[v].eb(u);
    }

    int a = 0, b = 1, c = -1; for (int v : G[a]) Sa.insert(v);
    for (int v : G[b]) if (Sa.find(v) != Sa.end()) c = v;

    int d = add_vertex(a, b, c);
    tree1 = {{a, d}, {d, c}, {c, b}};
    tree2 = {{c, a}, {a, b}, {b, d}};

    deg[a] = deg[b] = deg[c] = 2;
    que.push(a); que.push(b); que.push(c);
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (int v : G[u]) {
            ++deg[v];
            if (deg[v] == 2) {
                que.push(v);
                vector <int> vt;
                for (int w : G[v]) {
                    if (deg[w] >= 2) vt.eb(w);
                }
                assert(vt.size() == 2);
                tree1.eb(edge{v, vt[0]});
                tree2.eb(edge{v, vt[1]});
            }
        }
    }

    report(tree1);
    report(tree2);
}