给你一个由 $$$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
注意
示例第二个测试用例说明:
示例第三个测试用例说明: