## Tree of Life

View as PDF

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

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 A, C, G, and 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.

#### Constraints

is the sum of the lengths of the DNA sequences collected.

##### Subtask 1 [20%]

All DNA sequences only contain A.

#### Input Specification

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 G, C, A, or T. The string on the of the lines is , the DNA of the species represented by node .

#### 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