Out of all shortest path I am finding min of maximum distance I have to travel for every level.





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

void bfs(int u,vector<int> &d,const vector<vector<int>> adj){
    d[u] = 0;
    queue<int> q;
    q.push(u);

    while(!q.empty()){
        int u = q.front();
        q.pop();

        for(auto v:adj[u]){
            if(d[v]>d[u]+1){
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> adj(n);

    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u-1].push_back(v-1);
        adj[v-1].push_back(u-1);
    }

    vector<int> ds(n,1e9),df(n,1e9),dr(n,1e9);
    int s,f,r;
    cin>>s>>f>>r;
    s--,f--,r--;
    bfs(s,ds,adj);
    bfs(f,df,adj);
    bfs(r,dr,adj);

    vector<vector<int>> l(ds[f]+1);

    for(int i=0;i<n;i++){
        if(ds[i]+df[i]==ds[f]){
            l[ds[i]].push_back(i);
        }
    }
    int ans = INT_MAX;
    for(int i=0;i<=ds[f];i++){
        int a = INT_MIN;
        for(auto x: l[i]){
            a = max(a,dr[x]);
        }
        ans = min(a,ans);
    }

    cout<<ans;

    return 0;
}