题目描述

给定一个由 $n$ 个顶点和 $m$ 条边组成的图。不能保证给定的图是连通的。其中一些边已经是有向的，你不能改变它们的方向。其他边是无向的，你需要为所有这些无向边选择一个方向。

你需要以这样的方式为无向边定向，使得最终的图是有向无环的（即所有边都有方向且不包含有向环）。注意，你必须为所有无向边定向。

你需要回答 $t$ 个独立的测试用例。

输入格式

输入的第一行包含一个整数 $t$ $(1 ≤ t ≤ 2×10^4)$ —— 测试用例的数量。接下来是 $t$ 个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ $(2 ≤ n ≤ 2×10^5,\ 1 ≤ m ≤ min(2×10^5,\ n(n−1)/2))$ —— 图中顶点的数量和边的数量。

接下来的 $m$ 行描述图中的边。第 $i$ 条边由三个整数 $t_i$, $x_i$ 和 $y_i$ $(t_i ∈ [0,1],\ 1 ≤ x_i, y_i ≤ 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$) 的边）。

保证所有测试用例的 $n$ 和 $m$ 的总和不超过 $2×10^5$ $(∑n ≤ 2×10^5;\ ∑m ≤ 2×10^5)$。

输出格式

对于每个测试用例，如果无法通过为无向边定向使得最终的图是有向无环的，则输出 NO；否则在第一行输出 YES，并在接下来的 $m$ 行中按任意顺序输出最终有向无环图的所有边。注意，你不能改变已有向边的方向。如果有多个解，可以输出任意一个。

样例

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

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

提示

样例1解释

示例中第二个测试用例的解释：

示例中第三个测试用例的解释：