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.