代码打印

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int read()
{
	int r=0, f=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') {r=r*10+ch-'0'; ch=getchar();}
	return r*f;	
}
struct Node{
	int v,x,p;
	inline friend bool operator <(const Node &x,const Node &y){
		if(x.p==y.p)return x.x<y.x;
		return x.p<y.p;
	}
}a[N];
int f[N],ans[N],b[N],c[N][2];
int main()
{
	//freopen("testdata.in","r",stdin);
    int t=read();
    while(t--){
    	int flag=1,n=read(),m=read();
    	for(register int i=1;i<=n;++i){
		    b[i]=ans[i]=0;
			c[i][0]=0;c[i][1]=n;
		}
    	for(register int i=1;i<=m;++i){
    		a[i].v=read();a[i].x=read();a[i].p=read();
    		if(a[i].p==0)c[a[i].v][1]=min(c[a[i].v][1],a[i].x);
    		else c[a[i].v][0]=max(c[a[i].v][0],a[i].x);
    		b[a[i].v]=1;
		}
		for(register int i=2;i<=n;++i)
		    if(c[i][1]<c[i][0]){flag=0;break;}
		for(register int i=1;i<=m;++i){
			if(c[a[i].v][0]==0||c[a[i].v][1]==n)continue;
			a[i].x=c[a[i].v][1];a[i].p=0;
		}
		sort(a+1,a+m+1);
		int cnt=1,ff=0;f[1]=1;
		for(register int i=1;i<=m&&flag;++i)
		    if(a[i].p==0){
		    	if(ans[a[i].v])continue;
		    	if(a[i].x>=cnt){f[++cnt]=a[i].v;ans[a[i].v]=f[cnt-1];}
		    	else ans[a[i].v]=f[a[i].x];
			}
			else{
				if(!ff){
		            for(register int i=2;i<=n;++i)
		            if(!b[i]){f[++cnt]=i;ans[i]=f[cnt-1];}
		            ff=1;
				}
				if(ans[a[i].v])continue;
				if(a[i].x>cnt){flag=0;break;}
				else{f[++cnt]=a[i].v;ans[a[i].v]=f[cnt-1];}
			}
	    if(flag==0)printf("Ugly\n");
	    else{
	    	printf("Beautiful\n");
	    	for(register int i=2;i<=n;++i)
	    	    printf("%d %d\n",i,ans[i]);
		}
	}
	return (0-0);
}