You are a biologist studying an evolutionary tree. An evolutionary tree is a rooted tree showing the evolutionary relationships between several species. There are nodes numbered to , each of which represents a different species. The tree is rooted from node . 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 species in your evolutionary tree. The DNA of the species of node is represented as a string composed of the characters
T for . 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.
is the sum of the lengths of the DNA sequences collected.
Subtask 1 [20%]
All DNA sequences only contain
Subtask 2 [80%]
The first line contains a single integer .
The next lines each contain a single integer. These integers represent the tree. The integer on the of the lines represents the node which is the parent of the node . For convenience, it is guaranteed that this number is less than .
The next lines each contain a string composed of
T. The string on the of the lines is , the DNA of the species represented by node .
Output a single integer, the largest genetic similarity between two distant species. If there are no two distant species, output
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2