Biciak 갱단

Bajtazar는 운송 회사에서 일하며, 수도에 있는 창고(1번 도시)에서 주변 도시의 상점으로 건축 자재를 배달한다. Bajtocja에는 1번부터 $n$번까지 번호가 붙은 $n$개의 도시가 있고, 도시들은 $n-1$개의 도로로 연결되어 있다. 각 도로의 중간 지점에는 주유소가 하나씩 있다.

Bajtazar의 하루 일정은 항상 같다. 수도(1번 도시)에서 출발해 어떤 도시 $x$까지 가장 짧은 경로로 간 뒤, 같은 경로로 돌아온다.

Bajtazar의 아들 Bitek은 주유소에서 파는 Biciak 봉제인형의 팬이다. Biciak은 모두 $m$종이며 1번부터 $m$번까지 번호가 붙어 있다. 주유소마다 한 종류만 팔기 때문에, 모든 종류를 모으려면 여러 주유소를 다녀야 한다.

Bajtazar는 매일 아침 그날 서로 다른 Biciak을 몇 종류나 살 수 있을지 궁금해한다. 주유소의 판매 목록은 시간이 지나면서 바뀐다. Bajtazar의 질문에 답하는 프로그램을 작성하라.

첫 줄에 정수 $n$, $m$, $z$가 주어진다 ($2 \le n \le 100\,000$, $1 \le m, z \le 150\,000$). 각각 도시의 수, Biciak의 종류 수, 질의의 수이다.

이후 $n-1$개의 줄에는 정수 $a$, $b$, $c$가 주어진다 ($1 \le a, b \le n$, $1 \le c \le m$). 이는 도시 $a$와 도시 $b$ 사이에 도로가 있고, 그 도로의 주유소에서 종류 $c$의 Biciak을 판다는 뜻이다.

이후 $z$개의 줄에는 질의가 주어진다. 각 질의는 문자 하나와 그 뒤에 오는 정수 하나 또는 둘로 이루어진다.

• Z $x$는 Bajtazar가 도시 $x$까지 갈 때 서로 다른 Biciak을 몇 종류 살 수 있는지 묻는다 ($2 \le x \le n$).
• B $i$ $c$는 지금부터 입력 순서상 $i$번째 도로($1 \le i < n$)의 주유소에서 종류 $c$의 Biciak을 살 수 있게 된다는 뜻이다 ($1 \le c \le m$). 그 순간 주유소가 이미 종류 $c$를 팔고 있었다면 아무것도 바뀌지 않는다.

Z 질의는 적어도 하나 주어진다.

Z 질의마다 답을 나타내는 정수를 한 줄에 하나씩 출력한다.

수도에서 도시 6으로 가는 경로는 도시 1, 3, 4, 6을 지난다. 처음에는 이 경로의 주유소에서 Biciak 2, 3, 2를 팔고 있으므로 살 수 있는 것은 2종류이다. 1-3 도로 주유소의 판매 목록이 바뀐 뒤에는 경로에서 Biciak 1, 3, 2를 살 수 있으므로 3종류가 된다.