← 返回题目列表

Codeforces · 1385/E

E. 定向边缘

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

给你一个由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成的图。不保证给定的图是连通的。有些边已经有方向,您无法更改它们的方向。其他边是无向的,您必须为所有这些边选择某个方向。

您必须以这样的方式定向无向边,使得生成的图是有向且非循环的(即所有边都是有向的并且没有有向循环的图)。请注意,您必须定向所有无向边。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2})$$$) — 图中的顶点数和边数,分别。

接下来的 $$$m$$$ 行描述了图形的边缘。第 $$$i$$$ 条边由三个整数 $$$t_i$$$、$$$x_i$$$ 和 $$$y_i$$$ 描述 ($$$t_i \in [0; 1]$$$, $$$1 \le x_i, y_i \le n$$$) — 边的类型 ($$$t_i = 0$$$ 如果边是无向的并且$$$t_i = 1$$$(如果边是有向的)并且该边连接顶点(无向边连接顶点 $$$x_i$$$ 和 $$$y_i$$$,有向边从顶点 $$$x_i$$$ 到顶点 $$$y_i$$$)。保证图不包含自循环(即从顶点到自身的边)和多边(即对于每对 ($$$x_i, y_i$$$) 不存在其他对 ($$$x_i, y_i$$$) 或 ($$$y_i, x_i$$$))。

保证 sum $$$n$$$ 和 sum $$$m$$$ 不超过 $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$; $$$\sum m \le 2 \cdot 10^5$$$)。

输出

对于每个测试用例,如果不可能以生成有向无环图的方式引导无向边,则打印答案“NO”,否则在第一行和描述生成的有向无环图的边的 $$$m$$$ 行上打印“YES”(以任何顺序)。请注意,您无法更改已定向边的方向。如果有多个答案,您可以打印任何一个。

示例

输入 #1

4
3 1
0 1 3
5 5
0 2 1
1 1 5
1 5 4
0 5 2
1 3 5
4 5
1 1 2
0 4 3
1 3 1
0 2 3
1 2 4
4 5
1 4 1
1 1 3
0 1 2
1 2 4
1 3 2

输出 #1

YES
3 1
YES
2 1
1 5
5 4
2 5
3 5
YES
1 2
3 4
3 1
3 2
2 4
NO

注意

示例第二个测试用例说明:

示例第三个测试用例说明: