题目背景

题目译自 XXVIII Olimpiada Informatyczna – I etap Gang Biciaków。

题目描述

Bajtazar 在一家货运公司工作，他目前的工作是将建筑材料从 Bajtocji 的首都运输到附近城镇的商店。在 Bajtocji，有 $n$ 座城市（编号从 $1$ 到 $n$），这些城市通过 $n-1$ 条道路相互连接。每条道路上都有一个加油站。

Bajtazar 一天的工作是这样的：他从首都（编号为 $1$ 的城市）出发，沿着最短路径到达城市 $x$，再原路返回。

Bajtazara 的儿子 Bitek 非常喜欢加油站里卖的玩具狗。玩具狗一共有 $m$ 种（编号从 $1$ 到 $m$），但每个加油站只提供一种玩具狗，因此收集玩具狗并非一件轻松的事情。

现在给出 Bajtazara 每天前往的目的地，他想要知道他的儿子这天能够获得多少种玩具狗。麻烦的是，每个加油站里售卖的玩具狗的种类会发生变化，你能帮助他解决这个难题吗？

输入格式

输入第一行三个整数 $n,m,z$，分别代表 Bajtocji 的城市数，玩具狗的种类数，查询的次数。

接下来 $n-1$ 行，第 $i$ 行三个整数 $a_i,b_i,c_i$，代表第 $i$ 条道路连接城市 $a_i$ 和城市 $b_i$（$1 \leq a_i,b_i \leq n$），该道路上的加油站售卖的玩具狗种类为 $c_i$（$1 \leq c_i \leq m$）。

接下来 $z$ 行，每行描述一个询问或修改操作，格式如下：

• 询问操作：$\texttt{Z}\ x$ 表示 Bajtazara 想要知道，从首都出发到城市 $x$（$2 \leq x \leq n$），能收集到多少种玩具狗。
• 修改操作：$\texttt{B}\ i\ c$ 表示将第 $i$ 条道路上加油站售卖的玩具狗的类型改为 $c$（$1 \leq c \leq m$，注意如果该加油站本来就售卖 $c$ 类型玩具狗，执行该操作后将不会有任何影响）。

输出格式

对于每个 $\texttt{Z}$ 操作，输出一行一个整数，代表这一天 Bajtazara 的儿子能获得的玩具狗的种类数。

6 3 5
1 2 3
1 3 2
3 4 3
5 3 1
6 4 2
Z 5
Z 6
B 2 1
Z 5
Z 6

2
2
1
3

8 4 20
1 2 3
8 2 4
6 4 2
1 6 1
3 4 3
4 5 2
7 4 1
Z 2
Z 3
Z 4
Z 5
Z 6
Z 7
Z 8
B 4 4
B 3 3
B 7 4
B 2 3
Z 2
Z 3
Z 4
Z 5
Z 6
Z 7
Z 8
B 3 4
Z 7

1
3
2
2
1
2
2
1
2
2
3
1
2
1
1

提示

【样例解释1】：

注意该样例中存在一次修改操作，使得第二条道路上的加油站售卖的玩具狗的种类从 $2$ 变成了 $1$。

【数据范围】：

所有测试点均满足：$2 \leq n \leq 10^5$，$1 \leq m,z \leq 1.5 \times 10^5$，且至少存在一个 $\texttt{Z}$ 操作。