CF1583B Omkar and Heavenly Tree

Omkar 大人希望拥有一棵包含 $n$ 个节点的树（$3 \le n \le 10^5$），并让他的弟子们来构建这棵树。然而，Omkar 大人设置了 $m$ 个限制条件（$1 \le m < n$），以确保这棵树尽可能地“神圣”。 一棵包含 $n$ 个节点的树是一个连通无向图，包含 $n$ 个节点和 $n-1$ 条边。注意，对于任意两个节点，恰好存在一条简单路径连接它们，其中简单路径指的是一条路径，路径上的每个节点都只出现一次。 以下是一个树的示例：  每个限制由 $3$ 个两两不同的整数 $a$、$b$、$c$（$1 \le a, b, c \le n$）组成，表示节点 $b$ 不能出现在节点 $a$ 和节点 $c$ 之间的简单路径上。 你能帮助 Omkar 大人，成为他最信任的弟子吗？你需要为多组限制条件找到“神圣”的树。可以证明，在给定的限制条件下，总能构造出一棵满足要求的树。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$3 \leq n \leq 10^5$，$1 \leq m < n$），表示树的节点数和限制条件的数量。 接下来的 $m$ 行，每行包含三个整数 $a_i$、$b_i$、$c_i$（$1 \le a_i, b_i, c_i \le n$，$a_i$、$b_i$、$c_i$ 两两不同），表示节点 $b_i$ 不能出现在节点 $a_i$ 和节点 $c_i$ 之间的简单路径上。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出 $n-1$ 行，每行两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \neq v$），表示在节点 $u$ 和节点 $v$ 之间有一条边。输出的边必须构成一棵满足 Omkar 限制条件的树。

第一个样例的输出对应如下的树：  对于第一个限制，节点 $1$ 和 $3$ 之间的简单路径为 $1, 3$，不包含 $2$。节点 $3$ 和 $5$ 之间的简单路径为 $3, 5$，不包含 $4$。节点 $5$ 和 $7$ 之间的简单路径为 $5, 3, 1, 2, 7$，不包含 $6$。节点 $6$ 和 $4$ 之间的简单路径为 $6, 7, 2, 1, 3, 4$，不包含 $5$。因此，这棵树满足所有限制条件。 第二个样例的输出对应如下的树：  由 ChatGPT 4.1 翻译