CF1583B.Omkar and Heavenly Tree

Lord Omkar would like to have a tree with $n$ nodes ($3 \le n \le 10^5$) and has asked his disciples to construct the tree. However, Lord Omkar has created $m$ ($\mathbf{1 \le m \lt n}$) restrictions to ensure that the tree will be as heavenly as possible.

A tree with $n$ nodes is an connected undirected graph with $n$ nodes and $n-1$ edges. Note that for any two nodes, there is exactly one simple path between them, where a simple path is a path between two nodes that does not contain any node more than once.

Here is an example of a tree:

A restriction consists of $3$ pairwise distinct integers, $a$, $b$, and $c$ ($1 \le a,b,c \le n$). It signifies that node $b$ cannot lie on the simple path between node $a$ and node $c$.

Can you help Lord Omkar and become his most trusted disciple? You will need to find heavenly trees for multiple sets of restrictions. It can be shown that a heavenly tree will always exist for any set of restrictions under the given constraints.

奥姆卡尔大人希望拥有一棵包含 $n$ 个节点（$3 \le n \le 10^5$）的树，并已要求其门徒构造这棵树。然而，为确保该树尽可能“神圣”，奥姆卡尔大人制定了 $m$（$\mathbf{1 \le m \lt n}$）条限制条件。

一棵含 $n$ 个节点的树是一个具有 $n$ 个节点和 $n-1$ 条边的连通无向图。注意：对任意两个节点，它们之间恰好存在一条简单路径；所谓简单路径，是指连接两个节点、且不重复经过任一节点的路径。

以下是一棵树的示例：

每条限制条件由三个两两互异的整数 $a$、$b$ 和 $c$（$1 \le a,b,c \le n$）组成，表示节点 $b$ 不能位于节点 $a$ 与节点 $c$ 之间的简单路径上。

您能否助奥姆卡尔大人一臂之力，成为他最信赖的门徒？您需要为多组不同的限制条件分别构造出满足要求的“神圣之树”。可以证明：在题目给定的约束条件下，对任意一组限制条件，总存在至少一棵满足所有限制的神圣之树。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). Description of the test cases follows.

The first line of each test case contains two integers, $n$ and $m$ ($3 \leq n \leq 10^5$, $\mathbf{1 \leq m \lt n}$), representing the size of the tree and the number of restrictions.

The $i$-th of the next $m$ lines contains three integers $a_i$, $b_i$, $c_i$ ($1 \le a_i, b_i, c_i \le n$, $a$, $b$, $c$ are distinct), signifying that node $b_i$ cannot lie on the simple path between nodes $a_i$ and $c_i$.

It is guaranteed that the sum of $n$ across all test cases will not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$3 \leq n \leq 10^5$，$\mathbf{1 \leq m \lt n}$），分别表示树的大小和限制条件的数量。

接下来的 $m$ 行中，第 $i$ 行包含三个整数 $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$。

For each test case, output $n-1$ lines representing the $n-1$ edges in the tree. On each line, output two integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$) signifying that there is an edge between nodes $u$ and $v$. Given edges have to form a tree that satisfies Omkar's restrictions.

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

The output of the first sample case corresponds to the following tree:

For the first restriction, the simple path between $1$ and $3$ is $1, 3$, which doesn't contain $2$. The simple path between $3$ and $5$ is $3, 5$, which doesn't contain $4$. The simple path between $5$ and $7$ is $5, 3, 1, 2, 7$, which doesn't contain $6$. The simple path between $6$ and $4$ is $6, 7, 2, 1, 3, 4$, which doesn't contain $5$. Thus, this tree meets all of the restrictions.

The output of the second sample case corresponds to the following tree:

第一个样例的输出对应如下树：

对于第一条限制：节点 $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$。因此，该树满足所有限制条件。

第二个样例的输出对应如下树：