012 - ツリーキーボード

問題

PCK博士はコンピュータ用の画期的な入力デバイス、ツリーキーボードを開発した。このキーボードには、それぞれ$1$から$N$の番号が付けられた$N$個のキーが配置されており、それらが$N - 1$本のワイヤで配線されている。また、どのキーからもいくつかのワイヤをたどっていけば他のキーに到達できる。
キーボードの設定として、各キーには１つの文字を割り当てることができ、これらはいつでも自由に変更することができる。このキーボードでは、あるキー$s$を押して、次にキー$t$を押したとき、キー$s$からキー$t$に至る最短経路上にあるすべてのキーの文字が順番に1回ずつ入力される。このとき、キー$s$とキー$t$が同じキーだった場合、文字は一度だけ入力される。
ツリーキーボードの情報、キーボードの設定操作、入力操作が与えられたとき、各入力操作直後の時点までにコンピュータに入力された異なる文字列の数を求めるプログラムを作成せよ。

入力

入力は以下の形式で標準入力から与えられる。

$N$
$k_1$
$k_2$
$\vdots$
$k_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u$N-1 $v$N-1
$Q$
$q_1$
$q_2$
$\vdots$
$q_Q$

１行目にキーの数$N$($1 \leq N \leq 100,000$)が与えられる。続く$N$行に、キー$i$最初に設定されている英小文字$k_i$が与えられる。続く$N - 1$行にワイヤの情報が与えられる。$u_i$と$v_i$($1 \leq u_i \leq v_i \leq N$)は$i$番目のワイヤが繋ぐキーの番号である。
続く行に操作の数$Q$($1 \leq Q \leq 100,000$)が与えられる。続く$Q$行に各操作が以下の形式で与えられる。

1 $s$ $t$

または

2 $k$ $c$

$1 s t$は、キー$s$($1 \leq s \leq N$)とキー$t$($1 \leq t \leq N$)を順番に打つ入力操作を表す。$2 k c$は、キー$k$($1 \leq k \leq N$)の印字文字を英小文字$c$に変更する設定操作を表す。

出力

各入力操作後に、その時点までにコンピュータに入力された異なる文字列の数をそれぞれ１行に出力する。

入出力例

入力例

6
a
b
a
c
e
b
1 2
2 3
2 4
2 5
5 6
4
1 1 6
1 3 4
2 5 c
1 1 5

出力例

1
2
2