Travelling Sales

    1#include <bits/stdc++.h>
    2using namespace std;
    3int main(){
    4    ios::sync_with_stdio(0); cin.tie(0);
    5    int n, m; cin >> n >> m;
    6    vector<vector<int>> adj(n + 1);
    7    for(int i = 0; i < m; i++){
    8        int a, b; cin >> a >> b;
    9        adj[a].push_back(b); adj[b].push_back(a);
    10    }
    11    deque<int> dq;
    12    vector<int> dist(n + 1, INT_MAX);
    13    unordered_set<int> office;
    14    int k; cin >> k;
    15    for(int i = 0; i < k; i++){
    16        int c; cin >> c;
    17        office.insert(c);
    18    }
    19    dist[*office.begin()] = 0;
    20    dq.push_front(*office.begin());
    21    while(!dq.empty()){
    22        int cur = dq.front(); dq.pop_front();
    23        for(int nxt : adj[cur]){
    24            if(office.count(nxt) && dist[nxt] != 0){
    25                dist[nxt] = 0;
    26                dq.push_front(nxt);
    27            } else if(dist[cur] + 1 < dist[nxt]){
    28                dist[nxt] = dist[cur] + 1;
    29                dq.push_back(nxt);
    30            }
    31        }
    32    }
    33    int ans = *max_element(dist.begin() + 1, dist.end());
    34    cout << ans << '\n';
    35}