代码打印

#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstring>
#include<stack>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
struct node
{
	int l, r, id;
};
int n, m;
int a[N], fa[N];
node s[N];
bool cmp1(node a, node b)
{
	if(a.r == b.r) return a.l < b.l;
	return a.r < b.r; 
}
int find(int x)
{
	if(x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}
int main() {
	int t;
	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		for(int i = 1; i < n; ++i)
			s[i].l = 1, s[i].r = n, s[i].id = i + 1;
		for(int i = 1; i <= m; ++i)
		{
			int v, x, p;
			cin >> v >> x >> p;
			if(p == 0)
				s[v - 1].r = x;
			else
				s[v - 1].l = x;
		}
		sort(s + 1, s + n, cmp1);
		vector<vector<int> > ans(n + 1);
		for(int i = 1; i <=n; ++i)
			fa[i] = i;
		for(int i = 1; i < n; ++i)
		{
			int pos = find(s[i].l);
//			cout << pos << "\n"; 
			ans[pos].push_back(s[i].id);
			fa[s[i].l] = s[i].l + 1;
		}
		bool flag = false, pred = false;
		for(int i = 1; i <=n; ++i)
		{
			if(!ans[i].size()) flag = 1;
			else
			{
				if(flag)
				{
					cout << "Ugly\n";
					pred = 1;
					break;
				}
			}
		}
		if(!pred)
		{
			cout << "Beautiful\n";
			ans[0].push_back(1); 
			for(int i = 1; i <= n; ++i)
			{
				if(ans[i].size() == 0) break;
				for(int j = 0; j < ans[i].size(); ++j)
					cout << ans[i - 1][0] << " " << ans[i][j] << "\n";
			}
		}
	}
	return 0;
}