← 返回题目列表

Codeforces · 1583/B

B. 奥姆卡和天堂树

中文机器翻译题面 查看原题

Omkar 勋爵想要一棵有 $$$n$$$ 节点的树 ($$$3 \le n \le 10^5$$$) 并要求他的门徒建造这棵树。然而,Omkar 勋爵创建了 $$$m$$$ ($$$\mathbf{1 \le m < n}$$$) 限制,以确保这棵树尽可能像天堂一样。

具有 $$$n$$$ 节点的树是具有 $$$n$$$ 节点和 $$$n-1$$$ 边的连通无向图。请注意,对于任何两个节点,它们之间都存在一条简单路径,其中简单路径是两个节点之间不多次包含任何节点的路径。

这是一个树的示例:

限制由 $$$3$$$ 成对不同的整数、$$$a$$$、$$$b$$$ 和 $$$c$$$ ($$$1 \le a,b,c \le n$$$) 组成。它表示节点$$$b$$$ 不能位于节点$$$a$$$ 和节点$$$c$$$ 之间的简单路径上。

你能帮助奥姆卡勋爵并成为他最信任的弟子吗?你需要找到天树来应对多组限制。可以证明,在给定的约束下,对于任何一组限制,天树总是存在。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数,$$$n$$$ 和 $$$m$$$ ($$$3 \leq n \leq 10^5$$$, $$$\mathbf{1 \leq m < n}$$$),代表树的大小和限制的数量。

接下来的 $$$m$$$ 行的第 $$$i$$$ 包含三个整数 $$$a_i$$$、$$$b_i$$$、$$$c_i$$$ ($$$1 \le a_i、b_i、c_i \le n$$$、$$$a$$$、$$$b$$$、$$$c$$$ 是不同的),表示节点 $$$b_i$$$ 不能位于节点 $$$a_i$$$ 和 $$$c_i$$$ 之间的简单路径上。

保证所有测试用例的 $$$n$$$ 总和不会超过 $$$10^5$$$。

输出

对于每个测试用例,输出表示树中 $$$n-1$$$ 边的 $$$n-1$$$ 行。每行输出两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) 表示节点 $$$u$$$ 和 $$$v$$$ 之间有一条边。给定的边必须形成一棵满足 Omkar 限制的树。

示例

输入 #1

2
7 4
1 2 3
3 4 5
5 6 7
6 5 4
5 3
1 2 3
2 3 4
3 4 5

输出 #1

1 2
1 3
3 5
3 4
2 7
7 6
5 1
1 3
3 2
2 4

注意

第一个示例案例的输出对应于以下树:

第二个示例案例的输出对应于以下树: