分析

可以把给无向边一个方向的过程看作加有向边的过程。

如果在原来有向边组成的图中有环，那么无论如何加边都不可能变成一张 DAG，无解。

考虑到在 DAG 中，对于一条有向边 \((x \rightarrow y)\)，\(x\) 的拓扑序一定小于 \(y\)。所以根据这个来构造，在原图上求出拓扑序。对于一条无向边 \((x \rightarrow y)\)，如果 \(y\) 的拓扑序大于 \(x\) 的，那么就从 \(x\) 向 \(y\) 连一条边，否则就反过来。

题目中说图不一定连通，但是不影响判环和求拓扑序。

CODE

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int N=2e5+5;
int t, n, m, tot, in[N], topo[N];
int cnt, h[N], ver[N<<1], nxt[N<<1], w[N<<1];
pair<int,int> a[N];
void add(int x,int y) {
	ver[++cnt]=y, nxt[cnt]=h[x], h[x]=cnt;
}
bool toposort() {
	int num=0;
	queue<int> q;
	for(int i=1;i<=n;++i) if(!in[i]) q.push(i);
	while(q.size()) {
		int x=q.front(); q.pop();
		topo[x]=++num;
		for(int i=h[x];i;i=nxt[i]) {
			int y=ver[i];
			if(--in[y]==0) q.push(y);
		}
	}
	return num==n;
}
void init() {
	tot=cnt=0;
	for(int i=0;i<=n;++i) h[i]=in[i]=topo[i]=0;
}
void sol() {
	init();
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) {
		int op, x, y; scanf("%d%d%d",&op,&x,&y);
		a[++tot]=make_pair(x,y);
		if(op) {
			add(x,y), ++in[y];
		}
	}
	if(!toposort()) { puts("NO"); return; }
	puts("YES");
	for(int i=1;i<=m;++i) {
		int x=a[i].first, y=a[i].second;
        // 这里是直接存了所有边
        // 因为如果a[i]是有向边，那么topo[x]一定小于topo[y]，不影响
		if(topo[x]>topo[y]) printf("%d %d\n",y,x);
		else printf("%d %d\n",x,y);
	}
}
int main() {
	scanf("%d",&t);
	while(t--) sol();
}