必要条件から絞っていき,あとから十分性を確かめる.
必要条件:
任意の\(i \in K\)に対して,頂点\(p_{i}\)から距離\(d_{i}\)未満の頂点は 全て白で塗られている.
それ以外の頂点は白で塗るメリットが全くないので,黒で塗ってよい.
この塗り方をしたときに,条件を満たしているかを判定すればよい.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m; cin >> n >> m;
vvll to(n);
rep(i,m){
ll a, b; cin >> a >> b;
--a, --b;
to[a].push_back(b);
to[b].push_back(a);
}
ll k; cin >> k;
vll p(k), vd(k);
rep(i,k){
cin >> p[i] >> vd[i];
--p[i];
}
vll col(n, 1);
auto bfs = [&](ll src, ll x, ll type) -> bool {
bool f = false;
vll dis(n, INFL);
queue<ll> que;
auto push = [&](ll v, ll d) -> void {
if(type == 0){
if(d < x){
col[v] = 0;
}
if(d >= x) return; // なくてもよい
}
if(type == 1 && d == x && col[v] == 1) {
f = true;
return ;
}
if(vis[v]) return;
vis[v] = true;
que.push(v);
dis[v] = d;
};
push(src, 0);
while(que.size()){
ll cu = que.front(); que.pop();
ll d = dis[cu];
for(auto ne: to[cu]){
push(ne, d + 1);
}
}
return f;
};
// draw
rep(i,k){
bfs(p[i], vd[i], 0);
}
// check
rep(i,k){
if(!bfs(p[i], vd[i], 1)) {
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
rep(i,n){
cout << col[i] ;
}
return 0;
}