H. Syl 和美丽树
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

植树节到了，Syl 整装待发，准备种出一棵美丽的树。

Syl 对美丽的树是有着独到的要求的，她认为一棵有着编号为 $$$1\sim n$$$ 的 $$$n$$$ 个节点的树是美丽的，当且仅当这棵树满足 Syl 给出的 $$$m$$$ 个条件，其中每个条件形如 $$$(v,x,p=0/1)$$$，表示编号为 $$$1$$$ 的点与编号为 $$$v$$$ 的点之间至多/至少距离 $$$x$$$ 条边。

具体来说：

  • 如果一个条件是 $$$(v,x,0)$$$，则表示 $$$1$$$ 和 $$$v$$$ 之间至多要距离 $$$x$$$ 条边，即 $$$\mathrm{dis}(1,v)\le x$$$；
  • 如果一个条件是 $$$(v,x,1)$$$，则表示 $$$1$$$ 和 $$$v$$$ 之间至少要距离 $$$x$$$ 条边，即 $$$\mathrm{dis}(1,v)\ge x$$$。

请你告诉 Syl，要怎样种出一棵美丽的树呢？如果不存在满足条件的树，这代表 Syl 不再能种出美丽的树，请输出 'Ugly'。

请回顾：一棵大小为 $$$n$$$ 的树是一个有 $$$n$$$ 个节点，$$$n-1$$$ 条边的连通无向图，并且其中任意两个节点之间有且仅有一条简单路径。

Input

第一行，一个整数 $$$t$$$ $$$(1\le t\le 10^5)$$$，表示测试数据的组数。

对于每组测试数据，第一行输入两个整数 $$$n,m$$$ $$$(2\le n\le 2\cdot 10^5, 1\le m \le 2\cdot 10^5)$$$，表示树的大小和条件数量。

对于同一组测试数据接下来的 $$$m$$$ 行，每行包括三个整数 $$$v,x,p$$$ $$$(2\le v\le n, 1\le x\le n-1, p\in\{0,1\})$$$，表示一个条件。

保证所有测试数据的 $$$n$$$ 之和与 $$$m$$$ 之和都不超过 $$$2\cdot 10^5$$$，即 $$$\sum n,\sum m\le 2\cdot10^5$$$。

Output

对于每组测试数据，如果存在方案，先输出 'Beautiful'，然后输出 $$$n-1$$$ 行，每行两个整数 $$$u,v$$$，表示树的一条边 $$$(u,v)$$$。如果不存在满足条件的方案，输出 'Ugly'。

Example
Input
4 
5 4 
2 3 0 
3 2 1 
4 1 0 
5 3 1 
5 4 
2 1 0 
3 2 1 
4 1 0 
5 4 1 
5 6 
2 2 0 
2 2 1 
3 2 0 
3 1 1 
4 3 0 
5 4 1 
6 4 
2 1 0 
3 1 0 
4 3 1 
6 4 1
Output
Beautiful 
1 4 
4 2 
4 3 
3 5 
Ugly 
Beautiful 
1 3 
3 2 
2 4 
4 5 
Beautiful 
1 2 
1 3 
2 5 
5 4 
4 6