#include "island.h"
#include<bits/stdc++.h>
#define Yzl unsigned long long
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
#define lob lower_bound
#define pb emplace_back
typedef long long LL;

using namespace std;

const Yzl Lty=20120712;

const int MAXN=2e5+10;
int n;
int deg[MAXN];
vector<int> e[MAXN];
void add(int f,int t) {
	e[f].pb(t); e[t].pb(f);
	++deg[f]; ++deg[t];
}
bool vis[MAXN];
int g[MAXN];
//void add_vertex(int x,int y,int i) {
//	
//}
//void report(vector<array<int,2> > tr) {
//	for(auto t:tr) {
//		printf("%d %d\n",t[0],t[1]);
//	}
//	puts("");
//}
void construct_two_trees(int N, vector<int> U, vector<int> V){
	n=N;
	for(int i=0;i<n-3;++i) add(U[i]+1,V[i]+1);
	for(int i=1;i<=n;++i) {
		int nt=(i==n?1:i+1);
		add(i,nt);
	}
//	cout<<114514<<" ";
	vector<array<int,2> > t1,t2;
	for(int i=1;i<=n;++i) {
		if(deg[i]==2) {
			int x=e[i][0],y=e[i][1];
			add_vertex(x-1,y-1,i-1);
			add(n+1,x); add(n+1,y); add(n+1,i);
			t1.pb((array<int,2>){x-1,y-1}); t1.pb((array<int,2>){y-1,n}); t1.pb((array<int,2>){x-1,i-1});
			t2.pb((array<int,2>){x-1,n}); t2.pb((array<int,2>){i-1,n}); t2.pb((array<int,2>){y-1,i-1});
			vis[x]=vis[y]=vis[i]=vis[n+1]=1;
			for(auto t:e[x]) ++g[t];
			for(auto t:e[y]) ++g[t];
			for(auto t:e[i]) ++g[t];
			break;
		}
	}
	queue<int> q;
	for(int i=1;i<=n;++i) if(!vis[i]&&g[i]==2) q.push(i);
	while(!q.empty()) {
		int u=q.front(); q.pop(); vis[u]=1;
		bool pd=0;
		for(auto t:e[u]) {
			++g[t];
			if(vis[t]) {
				if(!pd) t1.pb((array<int,2>){u-1,t-1}),pd=1;
				else t2.pb((array<int,2>){u-1,t-1});
			}
			if(!vis[t]&&g[t]==2) q.push(t);
		}
	}
	report(t1); report(t2);
}