class Solution {
public:
    pair <int,int> bfs(vector<vector<int>> &g,int src,string s){
        queue<int> q;
        vector <int> dis(s.length(),-1);

        q.push(src);
        dis[src] = 1;
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(int i:g[cur]){
                if(s[i]!=s[cur] && dis[i]==-1){
                    q.push(i);
                    dis[i] = dis[cur]+1;
                }
            }
        }

        int maxNode,maxDis=INT_MIN;

        for(int i=0;i<dis.size();i++){
            if(dis[i]>maxDis)
            {
                maxDis = dis[i];
                maxNode = i;
            }
        }

        return {maxNode,maxDis};
    }
    int longestPath(vector<int>& parent, string s) {

        vector<vector<int>> g(parent.size());
        for(int i=1;i<parent.size();i++)
        {
            g[parent[i]].push_back(i);
            g[i].push_back(parent[i]);
        }

        int ans = -1;

        for(int i=0;i<parent.size();i++){
            auto m = bfs(g,i,s);
            auto n = bfs(g,m.first,s);

            ans = max(ans,n.second);
        }


        return ans;

    }
};