1790G - Tokens on Graph - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int inf=1e18;

pair<int,int> bfs(int n, vector<vector<int> >& adi, vector<bool>& b, vector<bool>& t){
    vector<int> dist(n, -1);
    deque<int> q;
    q.push_back(0);
    dist[0]=0;

    while(!q.empty()){
        int v=q.front();
        q.pop_front();

        if(t[v]) return {v, dist[v]};
        if(v!=0 && !b[v]) continue;

        for(auto u: adi[v]){
            if(dist[u]==-1){
                dist[u]=dist[v]+1;
                q.push_back(u);
            }
        }
    }
    return {-1,  -1};
}

int longest(int n, vector<vector<int> >& adi, vector<bool>& b, vector<bool>& t){

    vector<bool> tok(n, false);
    for(int v=0; v<n; v++){
        for(auto u: adi[v]){
            if(t[u]) tok[v]=true;
        }

        if(b[v] && tok[v]){
            for(auto u: adi[v]){
                if(b[u]){
                    return inf;
                }
            }
        }   
    }

    int cnt=0;
    for(int v=0; v<n; v++){
        if(!t[v]) continue;

        for(auto u: adi[v]){
            if(b[u]){
                cnt++;
                break;
            }
        }
    }

    return cnt;
}

bool possible(int d, int l){
    if(d==-1) return false;
    return l>=(d-1);
}

void solve(){
    int n, m;
    cin >> n >> m;

    int tok, bon;
    cin >> tok >> bon;
    vector<bool> t(n, false);
    vector<bool> b(n, false);
    for(int i=0; i<tok; i++){
        int x;
        cin >> x;
        t[x-1]=true;
    }
    for(int i=0; i<bon; i++){
        int x;
        cin >> x;
        b[x-1]=true;
    }

    vector<vector<int> > adi(n);
    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        adi[a].push_back(b);
        adi[b].push_back(a);
    }

    auto [v, d]=bfs(n, adi, b, t);
    if(v!=-1) t[v]=false;
    int l=longest(n, adi, b, t);

    if(possible(d, l)){
        cout << "YES\n";
        return;
    }

    auto [v2, d2]=bfs(n, adi, b, t);
    if(v!=-1) t[v]=true; 
    if(v2!=-1) t[v2]=false;
    int l2=longest(n, adi, b, t);

    if(possible(d2, l2)){
        cout << "YES\n";
    }
    else{
        cout << "NO\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while(t--){
        solve();
    }
}