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 20000$
$1\le S\le 100000$
All DNA sequences only contain A.

Subtask 2 [80%]

$1\le N\le 20000$
$1\le S\le 100000$

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