Time Limit: 3.0 s

Memory Limit: 512.0 MB

Description

Wasim loves Tree. Fortunately, His friend Roy somehow know it. Roy preapred a problem for him. The problem is very simple,

You are given a tree with \(N\) node and a string \(S\) consisting only lowercase characters (a-z) of length \(N\) where \(i\)-th character represents the character written on \(i\)-th node of the tree. Root of the tree is 1 and you need to find out the length of the largest palindromic path from the root. There are also Q query. In each query you have to update \(X\)-th node with chararcter \(C\).
Find out the longest palindromic path from the root after perfoming each query.

Palindrome is a word or a phrase that is the same whether you read it backwards or forwards.

Some example of palindrome: a, aa, aba, cbbc, ddddd, edcde etc.

Input

First line takes an integer \(N\) : number of nodes in tree and the length of the string \(S\)
second line takes a string \(S\)
next \(N-1\) line takes two integers \(u,v\) : means \(u\)-th node has an edge with \(v\)-th node
Then take an integer \(Q\) : number of queries
Next \(Q\) line takes an integer \(X\) and a character \(C\)

\(1 <= N <= 1000\)
\(1 <= Q <= 10^5\)
\(1 <= X <= N\)
C consists only lowercase letters.

Output

After perfoming a query print the length of the largest palindromic path from root for all Q queries.

Sample

5
ababa
1 2
2 3
1 4
1 5
3
3 c
4 d
1 c

2
2
3

intial string S ="ababa";

After first query, S = "abcba", we need to update 3rd node with character c.

all possible path from root 1,

a. string "a", it's a palindrome and length 1.

1 -> 2.

a -> b. string "ab", it's not a palindrome.

1 -> 2 -> 3.

a -> b -> c. string "abc", it's not a palindrome.

1 -> 4.

a -> b. string "ab", it's not a palindrome.

1 -> 5.

a -> a. string "aa", it's a palindrome and length 2.

so maximum palindromic path length is 2.