题解：CF2109D D/D/D

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll INF = 1e12;
const ll MAXN = 4e5 + 5;

ll t;
queue<tuple<ll, ll, ll>> q;  // num step par
ll dist[MAXN][2];
vector<ll> e[MAXN];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> t;

    while (t--) {
        while (!q.empty()) {
            q.pop();
        }

        ll n, m, l, min_odd = INF, Max1 = 0, Max2 = 0;
        cin >> n >> m >> l;
        for (register int i = 1; i <= n; i++) {
            for (register int j = 0; j <= 1; j++) {
                dist[i][j] = INF;
            }
        }

        for (register int i = 1; i <= l; i++) {
            ll temp;
            cin >> temp;
            Max1 += temp;

            if (temp % 2) min_odd = min(min_odd, temp);
        }

        Max2 = Max1 - min_odd;
        int par1 = Max1 % 2, par2 = Max2 % 2;

        for (register int i = 1; i <= m; i++) {
            ll u, v;
            cin >> u >> v;
            e[u].push_back(v);
            e[v].push_back(u);
        }

        q.push({1, 0, 0});
        dist[1][0] = 0;

        while (!q.empty()) {
            auto [num, step, par] = q.front();
            q.pop();

            for (auto &i : e[num]) {
                if (dist[i][(par + 1) % 2] > step + 1) {
                    q.push({i, step + 1, (par + 1) % 2});
                    dist[i][(par + 1) % 2] = step + 1;
                }
            }
        }

        for (register int i = 1; i <= n; i++) {
            if (dist[i][par1] <= Max1 || dist[i][par2] <= Max2)
                putchar('1');
            else
                putchar('0');
        }

        putchar('\n');

        for (register int i = 1; i <= n; i++) {
            e[i].clear();
        }
    }
}