graph_coloring

// url: https://atcoder.jp/contests/abc299/tasks/abc299_e
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dist[2001][2001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n,m;
    cin>>n>>m;
    vector <ll> adj[n+1];
    bool ans=true;
    ll color[n+1];
    for (ll i=1; i<=n; i++) color[i]=-1;
    for (ll i=1,x,y; i<=m; i++){
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for (ll i=1; i<=n; i++){
        bool visited[n+1]={0};
        visited[i]=true;
        queue<ll> q;
        q.push(i);
        while(!q.empty()){
            ll s=q.front();
            q.pop();
            for (auto u:adj[s]){
                if (visited[u]) continue;
                visited[u]=true;
                dist[i][u]=dist[i][s]+1;
                q.push(u);
            }
        }
    }
    ll k;
    cin>>k;
    if (k==0){
        color[1]=1;
    }
    else {
        vector<ll> W,B;
        ll x[k+1], y[k+1];
        for (ll i=1; i<=k; i++){
            cin>>x[i]>>y[i];
            for (ll j=1; j<=n; j++){
                if (dist[x[i]][j]<y[i]) W.push_back(j);
                if (dist[x[i]][j]==y[i]) B.push_back(j);
            }
            for (auto u:W){
                if (color[u]==-1){
                    color[u]=0;
                }
                if (color[u]==2){
                    color[u]=0;
                }
            }
            for (auto u:B){
                if (color[u]==-1){
                    color[u]=2;
                }
            }
            W.clear();
            B.clear();
        }
        for (ll i=1; i<=k; i++){
            for (ll j=1; j<=n; j++){
                if (dist[x[i]][j]==y[i]) B.push_back(j);
            }
            bool pass=false;
            for (auto u:B){
                if (color[u]==2){
                    color[u]=1;
                    pass=true;
                }
            }
            if (!pass){
                ans=false;
                break;
            }
            B.clear();
        }
    }
    for (ll i=1; i<=n; i++){
        if (color[i]==-1){
            color[i]=0;
        }
        if (color[i]==2){
            color[i]=1;
        }
    }
    if (ans){
        cout<<"Yes\n";
        for (ll i=1; i<=n; i++){
            cout<<color[i];
        }
    }
    else {
        cout<<"No";
    }
}