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 ๐ฆ.
Constraints
1โคn,mโค105
1โคx,yโคn
Output Format
Output a single integer denoting the largest value among all paths.
If the value can be inifnite, output -1 instead.