Longest Path with Alternating Letters in Tree

Each node of a tree is labeled a or b. Find the maximum number of nodes on a simple path in which adjacent nodes have different letters. The path does not have to pass through the root.

输入格式

This site's input: the first line contains N (1..100000), the second line contains N characters a/b, and the third line contains N parent indices (0-based); the root's parent is −1. The input is guaranteed to form exactly one tree, and the root may have any index.

输出格式

Output a single integer, the answer.

样例 1

输入：

2
ab
-1 0

输出：

2

样例 2

输入：

5
abbab
-1 0 0 0 2

输出：

3

样例 3

输入：

1
a
-1

输出：

1

样例说明

Example 1: the two nodes have different letters, so both can be visited; the answer is 2.

Example 2: the path 1—0—2 has letters b, a, b and length 3; there is no longer valid path.

Example 3: there is only the root, so the longest path contains 1 node.