1857

class Solution {
public:
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        int n = colors.length();
        vector<int> in(n, 0);
        vector<vector<int>> g(n);
        int cnt[n][26];
        memset(cnt, 0, sizeof cnt);
        int ans = 0;

        // Make adj list graph.
        for(auto &edge: edges){
            g[edge[0]].push_back(edge[1]);
            in[edge[1]]++;
        }

        // Push the vertices with 0 indegree to queue.
        queue<int> q;
        for(int i=0; i<n; i++){
            if(!in[i])
                q.push(i);
        }

        // BFS.
        while(!q.empty()){
            int node = q.front(); q.pop();
            int col = colors[node]-'a';
            cnt[node][col]++;
            ans = max(ans, cnt[node][col]);
            for(auto &child: g[node]){
                for(int i=0; i<26; i++){
                    cnt[child][i] = max(cnt[child][i], cnt[node][i]);
                }
                in[child]--;
                if(!in[child])
                    q.push(child);
            }
        }

        // Check for cycle in graph.
        for(int i=0; i<n; i++)
            if(in[i])
                return -1;

        return ans;
    }
};