疑似难点在于实现。机房同学扔给我的。

考虑拆点，把每一个入度都拆成一个点，称这些为 A 点。然后接着再按照 A 点的入边颜色进行区分，建颜色点（B 点），把 A 点指向对应颜色的 B 点。

B 点的出边是所有非同颜色的边，指向这些边对应入度的 A 点，排序以后前后缀优化建图即可。

点数和边数都是 $4m$ 差不多。

之后就变成找环，dfs 就好，构造方案考虑在 A 点上打信息，直接遍历环按顺序把信息输出就能得到结果。

时间复杂度 $O(m\log m)$，瓶颈在于排序。

感觉不是很好写啊，还没写完 /ll

重构第二版终于写出来了。

#include<bits/stdc++.h>
#define pi pair<int,int>
#define N 1000005
using namespace std;
int n,m;
map<int,int>mp[N];
vector<int>ve[N<<2];
int top;
int get(int x,int c){
    if(mp[x][c])return mp[x][c];
    return mp[x][c]=++top;
}
vector<pi>ev[N];
bool cmp(pi x,pi y){
    return x.second<y.second;
}
bool ins[N<<2];
stack<int>st;
bool vis[N<<2];
vector<int>ans;
void dfs(int x){
    vis[x]=1;
    st.push(x);
    ins[x]=1;
    for(int i:ve[x])
    if(ins[i]){
        while(1){
            if(st.top()<=m)
            ans.push_back(st.top());
            if(st.top()==i)return;
            st.pop();
        }
    }else if(!vis[i]){
        dfs(i);
        if(!ans.empty())return;
    }
    st.pop();
    ins[x]=0;
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    mp[i].clear(),ev[i].clear();
    top=m+1;
    for(int i=1;i<=(m<<2);i++)
    ve[i].clear();
    for(int i=1;i<=m;i++){
        int u,v,c;
        cin>>u>>v>>c;
        ve[i].push_back(get(v,c));
        ev[u].push_back({i,c});
    }
    for(int x=1;x<=n;x++){
        if(ev[x].empty())continue;
        sort(ev[x].begin(),ev[x].end(),cmp);
        int j=0;
        for(auto[c,i]:mp[x]){
            while(j<ev[x].size()&&ev[x][j].second<c){
                top++;
                ve[top].push_back(ev[x][j].first);
                if(j)ve[top].push_back(top-1);
                j++;
            }
            if(j)
            ve[i].push_back(top);
        }
        j=ev[x].size()-1;
        for(auto[c,i]:mp[x]|views::reverse){
            while(j>=0&&ev[x][j].second>c){
                top++;
                ve[top].push_back(ev[x][j].first);
                if(j!=ev[x].size()-1)
                ve[top].push_back(top-1);
                j--;
            }
            if(j!=ev[x].size()-1)
            ve[i].push_back(top);
        }
    }
    for(int i=1;i<=top;i++)
    ins[i]=vis[i]=0;
    st=stack<int>();
    ans.clear();
    for(int i=1;i<=top;i++)
    if(ans.empty()&&!vis[i])dfs(i);
    if(ans.empty()){
        cout<<"NO\n";
        return;
    }
    cout<<"YES\n";
    cout<<ans.size()<<' ';
    reverse(ans.begin(),ans.end());
    for(int i:ans)cout<<i<<' ';
    cout<<'\n';
}
int main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
// 这么说著──穆罕默达利用自己的手指滑过莫乌尔涅的剑刃。
// 连火药枪都打不穿的单眼鬼的皮肤，不会那么简单就受伤。
// 在尝试过两三次后，终于划出细小的伤口，血珠涌现出来。
// 他将血液滴在莫乌尔涅中间部位的金属片上。

//「调整开始【Start Tuning】。」

// 穆罕默达利像是在念古代语言似的，有点生硬地喊道。

// 朦胧的光芒催发而出。