撞了个题，还做过。
将所有奇度给他建个边权为 \(1\) 的虚边和对应的虚点，图上一定存在欧拉回路，给欧拉回路定向，记录这个边的入边权值为 \(1\) 还是为 \(2\)，优先走上一次走的边权。这样跑的话，会将边权抵消，可以取到答案上界，即相连边权为奇数的点数。
#include <bits/stdc++.h>
using namespace std;
inline char gc(){
static char buf[1048576],*pn=buf,*pe=buf;
return (pn==pe)&&(pe=(pn=buf)+fread(buf,1,1048576,stdin),pn==pe)?EOF:*pn++;
}
inline int read(){
int d=0;char x=gc();
while(x<'0'||x>'9') x=gc();
while(x>='0'&&x<='9') d=(d<<1)+(d<<3)+(x-48),x=gc();
return d;
}
struct edge{
int v,id,r;
};
const int maxn=1e6+10;
vector<edge> G[2][maxn];
int st[maxn][2];
int n,m,deg[maxn],val[maxn];
bool vis[maxn*4],ans[maxn*3];
void dfs(int u,int faw)
{
for(int &i=st[u][faw];i<G[faw][u].size();i++)
{
int v=G[faw][u][i].v,id=G[faw][u][i].id,r=G[faw][u][i].r;
if(vis[id])continue;
vis[id]=1;
if(id<=m)ans[id]=r;
dfs(v,faw);
}
faw^=1;
for(int &i=st[u][faw];i<G[faw][u].size();i++)
{
int v=G[faw][u][i].v,id=G[faw][u][i].id,r=G[faw][u][i].r;
if(vis[id])continue;
vis[id]=1;
if(id<=m)ans[id]=r;
dfs(v,faw);
}
}
int tsum[maxn];
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++)
{
int u,v,w;
u=read(),v=read(),w=read();
tsum[u]+=w;
tsum[v]+=w;
if(w==1)
{
G[0][u].push_back({v,i,0});
G[0][v].push_back({u,i,1});
}
else
{
G[1][u].push_back({v,i,0});
G[1][v].push_back({u,i,1});
}
deg[u]++;deg[v]++;
}
int cid=m;
int Ans=0;
for(int i=1;i<=n;i++)
if(tsum[i]&1)Ans++;
for(int i=1;i<=n;i++)
if(deg[i]&1)
{
++cid;
G[0][0].push_back({i,cid,0});
G[0][i].push_back({0,cid,1});
}
printf("%d\n",Ans);
for(int i=0;i<=n;i++)if(!vis[i])dfs(i,0);
for(int i=1;i<=m;i++)printf("%d",ans[i]+1);putchar('\n');
//for(int i=1;i<=n;i++)printf("%d ",val[i]);putchar('\n');
return 0;
}