题目描述

给定一个包含 $n$ 个顶点和 $m$ 条边的图。该图不保证连通。有些边已经被定向，并且它们的方向不能改变；其余边是无向边，你需要为每一条无向边选择一个方向。

你需要给所有无向边定向，使最终得到的图成为有向无环图，也就是说，最终所有边都有方向，并且图中不存在有向环。注意，每一条无向边都必须定向。

你需要处理 $t$ 个相互独立的测试用例。

输入格式

第一行包含一个整数 $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=0$ 表示一条连接 $x_i$ 与 $y_i$ 的无向边；
  • $t_i=1$ 表示一条从 $x_i$ 指向 $y_i$ 的有向边。

保证图中没有自环，也没有重边：对于任意一对顶点，至多出现一条连接它们的边，无论方向如何。

输出格式

对于每个测试用例：

• 如果无法给所有无向边定向，使最终图成为有向无环图，输出一行 NO。
• 否则，先输出一行 YES，然后输出 $m$ 行，每行两个整数 $u,v$，表示最终图中的一条有向边 $u\to v$。

输出边的顺序任意，但原本已有方向的边不能改变。如果存在多种合法方案，输出任意一种。

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
2 1
0 1 2

YES
1 2

1
3 3
1 1 2
1 2 3
1 3 1

NO

原题图示

原题样例中第二组数据的图：

原题样例中第三组数据的图：

数据范围

所有测试用例的顶点数之和与边数之和分别不超过 $2\cdot 10^5$，即 $\sum n\le 2\cdot10^5$ 且 $\sum m\le 2\cdot10^5$。

（$1\le t\le 2\cdot 10^4$）

（$t_i\in\{0,1\}$，$1\le x_i,y_i\le n$）