比较有启发性的题。
首先，设 \(a_u\) 为与点 \(u\) 相连的边权和，答案的上界显然是 \(\sum\limits_{i = 1}^n [a_u \bmod 2 = 1]\)。
之后我们把 P7816 「Stoi2029」以父之名第一篇题解的做法搬过来，也就是：
- 建一个虚点向原图度数为奇数的点连边权为 \(1\) 的边，以保证新图中每个点的度数都为偶数，
- 在新图上直接跑欧拉回路，顺便根据访问的方向给每条边定向。注意进入一个点时优先选择与入边边权相同的边出去，再选择不同的。
可以证明这样的构造方法能达到答案上界。对于 \(a_u \bmod 2 = 1\) 的点：
- 若 \(deg_u \bmod 2 = 1\)，也就是它向虚点连边，那么连完边后与 \(u\) 相连的边权为 \(1\) 和 \(2\) 的边的数量都为偶数，也就是我们总是能选择一条与入边边权相同的出边。这样减去向虚点连的边，符合条件。
- 若 \(deg_u \bmod 2 = 0\)，也就是它不向虚点连边，那么在原图中与 \(u\) 相连的边权为 \(1\) 和 \(2\) 的边的数量都为奇数。这样我们会恰好有一次入边边权与出边边权不等的情形，也满足条件。
对于 \(a_u \bmod 2 = 0\) 的点，因为它本来就不可能满足条件，所以不用管它。
于是我们就证明了这个构造方法是正确的。
注意图可能不连通。
code
// Problem: F. Mashtali: a Space Oddysey
// Contest: Codeforces - Codeforces Global Round 17
// URL: https://codeforces.com/problemset/problem/1610/F
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 1000100;
int n, m, deg[maxn], a[maxn], ans[maxn], b[maxn];
bool vis[maxn];
vector<pii> G[maxn][3];
void dfs(int u, int k) {
vis[u] = 1;
for (int t = k, o = 0; o < 2; ++o, t ^= 3) {
while (G[u][t].size()) {
pii p = G[u][t].back();
G[u][t].pop_back();
int v = p.fst, d = p.scd;
if (ans[d]) {
continue;
}
ans[d] = (u == b[d] ? 1 : 2);
dfs(v, t);
}
}
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1, u, v, d; i <= m; ++i) {
scanf("%d%d%d", &u, &v, &d);
++deg[u];
++deg[v];
a[u] += d;
a[v] += d;
G[u][d].pb(v, i);
G[v][d].pb(u, i);
b[i] = u;
}
for (int i = 1; i <= n; ++i) {
if (deg[i] & 1) {
G[i][1].pb(n + 1, m + i);
G[n + 1][1].pb(i, m + i);
}
}
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
dfs(i, 1);
}
}
int cnt = 0;
for (int i = 1; i <= n; ++i) {
cnt += (a[i] & 1);
}
printf("%d\n", cnt);
for (int i = 1; i <= m; ++i) {
printf("%d", ans[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}