发现每次移动都会改变奇偶性，所以说想要判断合不合法很容易，就是判断原本的图中每个连通块是不是二分图就好。这个时候对于一个颜色就全是 22，剩下的一个颜色都填 11 或者 33。

但是题目要求构造出答案，假设数字是 22 的颜色都为白色，那么就会出现一个问题：对于同一个连通块里，颜色为白色的可能会有两种取值。

这个时候会发现 nn 非常小，于是我们可以跑一个背包 dp 来判断从 00 开始，在每个连通块里选一个点个数的取值，最后看能不能凑出 n2n_2，顺便随手记一下上一个的状态。

构造的时候就从 n2n_2 往回跳，然后对于白色点就放 22，剩下的点都任意放 1,31,3 都是满足题目条件的，直接随便构造就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
int n1, n2, n3;
vector<int> edges[5004];
vector<vector<int>> v0, v1; 
signed main()
{
    cin >> n >> m;
    cin >> n1 >> n2 >> n3;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    vector<int> c(n + 1, -1);
    function<void(int, int)> dfs = [&](int x, int idx) -> void {
        for (auto nex : edges[x]) {
            if (c[nex] != -1) {
                if (c[nex] == c[x]) {
                    cout << "NO";
                    exit(0);
                }
            } else {
                c[nex] = 1 - c[x];
                if (c[nex] == 0) {
                    v0[idx].push_back(nex);
                } else {
                    v1[idx].push_back(nex);
                }
                dfs(nex, idx);
            }
        }
    };
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (c[i] == -1) {
            c[i] = 0;
            cnt++;
            v0.push_back({i});
            v1.push_back({});
            dfs(i, v0.size() - 1);
        }
    }
    vector<vector<bool>> dp(cnt + 1, vector<bool>(n2 + 1, 0));
    dp[0][0] = 1;
    vector<vector<int>> ls(cnt + 1, vector<int>(n2 + 1, -1));
    for (int i = 1; i <= cnt; i++) {
        for (int j = 0; j <= n2; j++) {
            if (j >= (int)v0[i - 1].size() && dp[i - 1][j - (int)v0[i - 1].size()]) {
                dp[i][j] = 1;
                ls[i][j] = 0;
            }
            if (j >= (int)v1[i - 1].size() && dp[i - 1][j - (int)v1[i - 1].size()]) {
                dp[i][j] = 1;
                ls[i][j] = 1;
            }
        }
    }
    if (dp[cnt][n2] == 0) {
        cout << "NO" << '\n';
        return 0;
    }
    cout << "YES" << '\n';
    vector<bool> vis(cnt + 1, 0);
    int pos = n2;
    for (int i = cnt; i >= 1; i--) {
        vis[i] = ls[i][pos];
        pos -= (ls[i][pos] == 0 ? (int)v0[i - 1].size() : (int)v1[i - 1].size());
    }
    int cntt = 0;
    vector<int> ans(n + 1);
    for (int i = 0; i < cnt; i++) {
        if (vis[i + 1] == 1) {
            swap(v0[i], v1[i]);
        }
        for (int j = 0; j < v0[i].size(); j++) {
            ans[v0[i][j]] = 2;
        }
        for (int j = 0; j < v1[i].size(); j++) {
            if (cntt < n1) {
                ans[v1[i][j]] = 1;
                cntt++;
            } else {
                ans[v1[i][j]] = 3;
                cntt++;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i];
    }
    return 0;
}