There is a state with 𝑛 cities and 𝑚 uni-directional roads connecting those cities. One lowercase alphabet (‘a’-‘z’) is assigned to each city. We define a path’s value as the count of the most occurring letter. If letters on the cities encountered on a path are “abbabacca”, then the value of that path is 4 as ‘a’ is the most frequent letter and its count is 4. Find the maximum possible value among all paths.
The first line contains an integer T denoting the number of test cases. For each test case, first line contains two positive integers 𝑛 , 𝑚 (1≤𝑛,𝑚≤105), denoting that the state has 𝑛 cities and 𝑚 directed roads.
The second line contains a string 𝑠 with only lowercase letters. The 𝑖th character is the letter assigned to the 𝑖thcity.
Then 𝑚 lines follow. Each line contains two integers 𝑥,𝑦 (1≤𝑥,𝑦≤n), describing a directed edge from 𝑥 to 𝑦.
Output a single integer denoting the largest value among all paths.
If the value can be inifnite, output -1 instead.