Longest Path With Different Adjacent Characters

A tree is rooted at 0, and each node carries a lowercase letter. Return the maximum number of nodes on any simple path in which every pair of adjacent nodes has different characters.

输入格式

This site's ranges: the first line contains N (1..100000), the second line contains N parent values (parent[0]=−1; the others are 0-based parent indices), and the third line contains N lowercase letters. The input is guaranteed to be a valid tree.

输出格式

Output a single integer, the answer.

样例 1

输入：

6
-1 0 0 1 1 2
abacbe

输出：

3

样例 2

输入：

4
-1 0 0 0
aabc

输出：

3

样例 3

输入：

1
-1
z

输出：

1

样例说明

Example 1: 0—1—3 has distinct characters a, b, c, so the longest path has 3 nodes.

Example 2: 2—0—3 with b, a, c forms a path of length 3.

Example 3: there is only one node, so the answer is 1.