题目：
给定一个由 n 个点和 m 条边构成的图。
不保证给定的图是连通的。
图中的一部分边的方向已经确定，你不能改变它们的方向。
剩下的边还未确定方向，你需要为每一条还未确定方向的边指定方向。
你需要保证在确定所有边的方向后，生成的图是一个有向无环图（即所有边都是有向的且没有有向环的图）。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含两个整数 n,m。
接下来 m 行，每行包含三个整数 t,x,y，用来描述一条边的信息，其中 t 表示边的状态，如果 t=0，则表示边是无向边，如果 t=1，则表示边是有向边。x,y 表示这条边连接的两个端点，如果是有向边则边的方向是从 x 指向 y。
保证图中没有重边（给定了 (x,y)，就不会再次出现 (x,y) 或出现 (y,x)）和自环（不会出现 x=y 的情况）。
输出格式
对于每组数据，如果无法构造出有向无环图，则输出一行 NO。
否则，先输出一行 YES，随后 m 行，每行包含两个整数 x,y，用来描述最终构造成的有向无环图中的每条边的具体方向（x 指向 y），边的先后顺序随意。
注意，已经确定方向的边，不能更改方向。
如果答案不唯一，输出任意合理方案均可。
数据范围
对于前三个测试点，1≤n,m≤10。
对于全部测试点，1≤T≤20000，2≤n≤2×105，1≤m≤min(2×105,n(n−1)2)，0≤t≤1，1≤x,y≤n。
保证在一个测试点中，所有 n 的和不超过 2×105，所有 m 的和不超过 2×105。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef pair<int,int> PII;
const int N = 2e5+10, M = 2*N;
int e[M],ne[M],h[N],idx;
PII p1[M];
PII p2[M];
int d[N];
int cnt1,cnt2;
int n,m;
int q[N];
int pos[N];
int cnt[N];
/*
性质：
如果有向边已经成环了 就无解
如果有向边是拓扑的，那么就一定有解
*/
bool topsort()
{
int tt = -1,hh=0;
for(int i = 1;i<=n;i++)
if(!d[i]) q[++tt] = i;
while(hh<=tt)
{
int t =q[hh++];
for(int i = h[t];~i;i=ne[i])
{
int j =e[i];
d[j]--;
if(!d[j]) q[++tt] = j;
}
}
return tt==n-1;
}
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(d,0,sizeof d);
memset(h,-1,sizeof h);
idx = cnt2 = cnt1 = 0;
scanf("%d%d",&n,&m);
for(int i = 0;i<m;i++)
{
int t,x,y;
scanf("%d%d%d",&t,&x,&y);
if(t==0)
p2[cnt2++]= {x,y};
else
{
add(x,y);
p1[cnt1++] = {x,y};
d[y]++;
}
}
if(topsort())
{
puts("YES");
for(int i = 1;i<=n;i++)
for(int j = h[i];~j;j=ne[j])
{
printf("%d %d\n",i,e[j]);
}
for(int i = 0;i<n;i++) pos[q[i]] = i;
for(int i = 0;i<cnt2;i++)
{
int a = p2[i].first,b = p2[i].second;
if(pos[a]>pos[b]) swap(a,b);
printf("%d %d\n",a,b);
}
}
else
{
puts("NO");
}
}
return 0;
}