seuOJ564 - Syl 和美丽树

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：1024 MiB
• 题目标签：夏季, 2025

题目描述

植树节到了，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$ 条边的连通无向图，并且其中任意两个节点之间有且仅有一条简单路径。

输入格式

第一行，一个整数 $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$。

输出格式

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

样例

输入样例

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

输出样例

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