Need help for this problem

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.

Input Format

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 Format

Output a single integer denoting the largest value among all paths.

If the value can be inifnite, output -1 instead.