# 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 π¦.

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.