ABC 299

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vvint graph(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int K;
    cin >> K;
    vector<pair<int, int>> ps;
    rep(i, K) {
        int p, d;
        cin >> p >> d;
        p--;
        ps.push_back({p, d});
    }

    auto short_path = [](vvint& graph, int start) -> vint {
        int N = graph.size();
        vint dist(N, INF);
        dist[start] = 0;

        // cost, position
        using P = pair<ll, int>;
        deque<P> deq;
        deq.push_back({0, start});
        while (deq.size()) {
            auto [cost, now] = deq.front();
            deq.pop_front();

            if (dist[now] < cost)
                continue;

            for (int nx : graph[now]) {
                if (dist[nx] <= cost + 1)
                    continue;
                dist[nx] = cost + 1;
                deq.push_back({cost + 1, nx});
            }
        }

        return dist;
    };

    vvint dists(N);
    rep(i, N) {
        dists[i] = short_path(graph, i);
    }

    // 一旦全ての頂点を黒く塗る
    vint black(N, 1);

    // 頂点 p から d より近いところにある黒を白く塗り直す
    for (auto [p, d] : ps) {
        rep(i, N) {
            if (dists[p][i] < d)
                black[i] = 0;
        }
    }

    // 各頂点について条件を満たす黒い頂点があるか調べる
    for (auto [p, d] : ps) {
        int ok = 0;
        rep(i, N) {
            if (dists[p][i] == d && black[i])
                ok = 1;
        }
        if (!ok) {
            yesno(false);
            return;
        }
    }

    yesno(true);
    for (int x : black)
        cout << x;
    cout << endl;
}