You are a biologist studying an evolutionary tree. An evolutionary tree is a rooted tree showing the evolutionary relationships between several species. There are ~N~ nodes numbered ~1~ to ~N~, each of which represents a different species. The tree is rooted from node ~1~. Two species are said to be distant if neither of their corresponding nodes are descendants of the other.

You have collected the DNA sequences of all ~N~ species in your evolutionary tree. The DNA of the species of node ~i~ is represented as a string ~S_i~ composed of the characters A, C, G, and T for ~1 \le i \le N~. The genetic similarity of two species is the length of the longest common substring of their DNA sequences.

Find the largest genetic similarity between two distant species.

Constraints

~S~ is the sum of the lengths of the ~N~ DNA sequences collected.

Subtask 1 [20%]

~1 \le N \le 20\,000~
~1 \le S \le 100\,000~
All DNA sequences only contain A.

Subtask 2 [80%]

~1 \le N \le 20\,000~
~1 \le S \le 100\,000~

Input Specification

The first line contains a single integer ~N~.
The next ~N-1~ lines each contain a single integer. These integers represent the tree. The integer on the ~i^\text{th}~ of the ~N-1~ lines represents the node which is the parent of the node ~i+1~. For convenience, it is guaranteed that this number is less than ~i+1~.
The next ~N~ lines each contain a string composed of G, C, A, or T. The string on the ~i^\text{th}~ of the ~N~ lines is ~S_i~, the DNA of the species represented by node ~i~.

Output Specification

Output a single integer, the largest genetic similarity between two distant species. If there are no two distant species, output -1.

Sample Input 1

3
1
2
ACT
GG
AGG

Sample Output 1

-1

Sample Input 2

3
1
1
ACT
GG
AGG

Sample Output 2

2