CF1385E.Directing Edges

You are given a graph consisting of $n$ vertices and $m$ edges. It is not guaranteed that the given graph is connected. Some edges are already directed and you can't change their direction. Other edges are undirected and you have to choose some direction for all these edges.

You have to direct undirected edges in such a way that the resulting graph is directed and acyclic (i.e. the graph with all edges directed and having no directed cycles). Note that you have to direct all undirected edges.

You have to answer $t$ independent test cases.

给你一个包含 $n$ 个顶点和 $m$ 条边的图。该图不保证连通。部分边已有方向，你不能改变这些边的方向；其余边是无向的，你需要为所有这些无向边指定一个方向。

你需要为无向边指定方向，使得最终得到的图是有向无环图（即所有边均有方向，且图中不存在有向环）。注意：你必须为所有无向边指定方向。

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

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2})$) — the number of vertices and the number of edges in the graph, respectively.

The next $m$ lines describe edges of the graph. The $i$-th edge is described with three integers $t_i$, $x_i$ and $y_i$ ($t_i \in [0; 1]$, $1 \le x_i, y_i \le n$) — the type of the edge ($t_i = 0$ if the edge is undirected and $t_i = 1$ if the edge is directed) and vertices this edge connects (the undirected edge connects vertices $x_i$ and $y_i$ and directed edge is going from the vertex $x_i$ to the vertex $y_i$). It is guaranteed that the graph do not contain self-loops (i.e. edges from the vertex to itself) and multiple edges (i.e. for each pair ($x_i, y_i$) there are no other pairs ($x_i, y_i$) or ($y_i, x_i$)).

It is guaranteed that both sum $n$ and sum $m$ do not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$; $\sum m \le 2 \cdot 10^5$).

输入的第一行包含一个整数 $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\left(2 \cdot 10^5, \frac{n(n-1)}{2}\right)$），分别表示图中顶点的数量和边的数量。

接下来的 $m$ 行描述图中的边。第 $i$ 条边由三个整数 $t_i$、$x_i$ 和 $y_i$ 描述（其中 $t_i \in [0, 1]$，$1 \le x_i, y_i \le n$）：$t_i$ 表示该边的类型（若 $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 \cdot 10^5$（即 $\sum n \le 2 \cdot 10^5$；$\sum m \le 2 \cdot 10^5$）。

For each test case print the answer — "NO" if it is impossible to direct undirected edges in such a way that the resulting graph is directed and acyclic, otherwise print "YES" on the first line and $m$ lines describing edges of the resulted directed acyclic graph (in any order). Note that you cannot change the direction of the already directed edges. If there are several answers, you can print any.

对于每个测试用例，请输出答案：如果无法将无向边定向，使得最终得到的图是有向无环图，则输出“NO”；否则，在第一行输出“YES”，并在接下来的 $m$ 行中描述所得有向无环图的各条边（顺序任意）。注意：你不能改变已有的有向边的方向。若存在多种可行方案，输出任意一种即可。

Explanation of the second test case of the example:

Explanation of the third test case of the example:

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

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