PCK博士はコンピュータ用の画期的な入力デバイス、ツリーキーボードを開発した。このキーボードには、それぞれ$1$から$N$の番号が付けられた$N$個のキーが配置されており、それらが$N-1$本のワイヤで配線されている。また、どのキーからもいくつかのワイヤをたどっていけば他のキーに到達できる。
キーボードの設定として、各キーには１つの文字を割り当てることができ、これらはいつでも自由に変更することができる。このキーボードでは、あるキー$s$を押して、次にキー$t$を押したとき、キー$s$からキー$t$に至る最短経路上にあるすべてのキーの文字が順番に1回ずつ入力される。このとき、キー$s$とキー$t$が同じキーだった場合、文字は一度だけ入力される。
ツリーキーボードの情報、キーボードの設定操作、入力操作が与えられたとき、各入力操作直後の時点までにコンピュータに入力された異なる文字列の数を求めるプログラムを作成せよ。
入力は以下の形式で与えられる。
$N$
$k_1$
$k_2$
:
$k_N$
$u_1$ $v_1$
$u_2$ $v_2$
:
$u_{N-1}$ $v_{N-1}$
$Q$
$q_1$
$q_2$
:
$q_Q$
１行目にキーの数$N$ ($1 \leq N \leq 100,000$)が与えられる。続く$N$行に、キー $i$に最初に設定されている英小文字$k_i$が与えられる。続く$N-1$行にワイヤの情報が与えられる。$u_i$と$v_i$ ($1 \leq u_i < 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