题 目 链 接

思维构造题，个人感觉这个拓扑序好难哦~

题意：给一个图，图中有有向边和无向边，对于每个无向边赋一个方向，问是否能使得图无环。

分析一下：

直接上结论：如果用有向边组成的图无环，则对无向边赋方向一定能无环。

证明：（反证法）
上面结论的反面就是，一条无向边无论选哪个方向都会成环；
则我们可以画个图，发现如果无论选哪个方向都会成环；
则原来的有向边就能组成环了，和条件矛盾，证明完毕。

递推一下：对于一条无向边是这样，那么对于整个图的无向边也是这样的。

那么问题就变成了两个：
1. 如何判断用有向边组成的图是否有环？
2. 对无向边如何构造方向能无环？

1的话可以直接有向边建图，拓扑序一下就行；

2的话我们画个图：a -> b -> c - a；
如果这个要形成环，则要c -> a；（即后面的点要向前面的点连）
再根据我们拓扑序的原理，要成环 <=> 时间戳大的点 -> 时间戳小的点；
反过来，不成环 的话，我们构造 时间戳小的点 -> 时间戳大的点 就行(c <- a)
而这个时间戳就可以用拓扑序顺便求出来！
即我们按照拓扑序对无向边赋方向就行！

妙啊~

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<cmath> 
#include<algorithm>
#include<deque>
#include<stack>
#include <unordered_map>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;

#define pb push_back
#define coutt cout<<"------------"<<endl;
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> PII;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;

const int maxn = 1e6 + 7;
const int N = 2e5+7;
const int M = 1e6+7;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = 3.14159265359;

ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}

struct node
{
    int ty;
    int u,v;
}no[maxn];

vector<int> g[maxn];

int din[maxn];  //入度
int ans[maxn];  //记录每个点的拓扑序
int idx;
int n,m;

void topsort()
{
    queue<int> q;
    idx = 0;

    for(int i=1;i<=n;i++)
        if(din[i] == 0)
            q.push(i);

    while(q.size())
    {
        int u = q.front();
        q.pop();

        ans[u] = ++idx;

        for(auto v : g[u])
        {
            din[v] --;
            if(din[v] == 0) q.push(v);
        }
    }
}

void solve()
{
    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;i++)
    {
        g[i].clear();
        din[i] = 0;
    }

    for(int i=1;i<=m;i++)
    {
        int ty,a,b;
        scanf("%d %d %d",&ty,&a,&b);

        no[i] = {ty,a,b};

        if(ty)  //有向边
        {
            din[b] ++;
            g[a].push_back(b);
        }
    }

    topsort();

    if(n > idx)
    {
        cout<<"NO"<<endl;
        return;
    }

    cout<<"YES"<<endl;
    for(int i=1;i<=m;i++)
    {
        int u = no[i].u;
        int v = no[i].v;

        if(ans[u] < ans[v]) printf("%d %d\n",u,v);
        else printf("%d %d\n",v,u);
    }
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }

    return 0;
}