先将无向图转为一个 DAG，直接从大点向小点连边就可以。
考虑增量构造，假设当前已经构造完了集合 \({1,2,\cdots,i-1}\)，他们满足有边的点权值不同。现在我们加入第 \(i\) 个点。那么枚举他的出边，将出点按点权分为两类。如果我们最初令所有边权都为 \(1\)，那么当前点的出边边权也都为 \(1\)，所以出点点权为 \(0\) 可以通过将点权 \(+1\)，边权 \(-1\) 的方式使得 \(i\) 号点的点权减 \(1\)，同时这个点原本的权值不变。同理点权为 \(0\) 的出点可以使 \(i\) 号点的点权 \(+1\) 。于是可以得到 \(deg_i+1\) 种不同的点权，根据抽屉原理可得一定有一个点权和出点都不同。
复杂度 \(O(n+k)\)。
#include<bits/stdc++.h>
#define N 2001001
#define MAX 5005
#define inf 1e18
using namespace std;
typedef long long ll;
typedef long double db;
inline void read(ll &ret)
{
ret=0;char c=getchar();bool pd=false;
while(!isdigit(c)){pd|=c=='-';c=getchar();}
while(isdigit(c)){ret=(ret<<1)+(ret<<3)+(c&15);c=getchar();}
ret=pd?-ret:ret;
return;
}
ll n,k,x,y,val[N],cv[N],ce[N],fr[N],ed[N];
bool vis[N];
vector<pair<ll,ll> >v[N];
signed main()
{
read(n);
read(k);
for(int i=1;i<=k;i++)
{
read(x);
read(y);
fr[i]=x,ed[i]=y;
val[x]++,val[y]++;
ce[i]=1;
if(x<y)
v[y].push_back(make_pair(x,i));
else
v[x].push_back(make_pair(y,i));
}
for(int i=1;i<=n;i++)
{
ll cnt0=0,cnt1=0;
for(auto j:v[i])
{
ll x=j.first;
if(cv[x]==0)
cnt0++;
else
cnt1++;
vis[val[x]]=true;
}
for(int j=val[i]-cnt0;j<=val[i]+cnt1;j++)
{
if(!vis[j])
{
if(j<val[i])
{
ll now=val[i]-j;
for(auto t:v[i])
{
if(cv[t.first]==0&&now)
now--,ce[t.second]=0,cv[t.first]=1;
}
}
else
{
ll now=j-val[i];
for(auto t:v[i])
{
if(cv[t.first]==1&&now)
now--,ce[t.second]=2,cv[t.first]=0;
}
}
val[i]=j;
break;
}
}
for(auto j:v[i])
{
ll x=j.first;
vis[val[x]]=false;
}
}
ll ans=0;
for(int i=1;i<=n;i++)
ans+=cv[i];
printf("%lld\n",ans);
for(int i=1;i<=n;i++)
if(cv[i])
printf("%d ",i);
if(ans)
puts("");
for(int i=1;i<=k;i++)
printf("%lld %lld %lld\n",fr[i],ed[i],ce[i]);
exit(0);
}