A directed graph has n nodes numbered 0 .. n-1; node i is painted with the colour colours[i], a lowercase letter, so n = len(colours). The list edges holds directed edges [u, v] (from u to v).
A route is any sequence of nodes where each consecutive pair is joined by an edge in the right direction; a single node is a route too. The score of a route is the largest number of times one colour appears among its nodes. Return the highest score over all routes, or -1 if the graph contains a directed cycle (then scores are unbounded).
Examples
Input: colours = "abaca", edges = [[0, 1], [0, 2], [2, 3], [3, 4]]
Output: 3
Explanation: the route 0 -> 2 -> 3 -> 4 has colours a, a, c, a.
Input: colours = "ab", edges = [[0, 1], [1, 0]]
Output: -1
Input: colours = "z", edges = []
Output: 1
Constraints
1 <= n <= 10**4,0 <= len(edges) <= 2 * 10**4,0 <= u, v < n; self-loops count as cycles- Target: O(26 * (n + E)) time.
Goals
- Run a DP in topological order with a small vector of states per node
- Detect a cycle with the same Kahn pass that drives the DP