CF1385E Directing Edges

给定一个包含 $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)$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，$m$ 的总和也不超过 $2 \cdot 10^5$（$\sum n \le 2 \cdot 10^5$，$\sum m \le 2 \cdot 10^5$）。

对于每个测试用例，输出一行答案——如果无法将所有无向边定向，使得最终图为有向无环图，则输出 "NO"；否则，先输出一行 "YES"，再输出 $m$ 行，描述最终得到的有向无环图中的所有边（顺序任意）。注意，已定向的边方向不能改变。如果有多种方案，输出任意一种均可。

第二个样例的解释：  第三个样例的解释：  由 ChatGPT 4.1 翻译