Bessie의 눈 소

농장에 눈이 내려, Bessie는 겨울마다 그랬듯이 눈으로 소를 만들고 있다. 보통은 실제 소와 최대한 비슷하게 만들지만, 올해는 추상적인 작품을 만들기로 하고 나무 모양의 조각을 만든다. 이 조각은 $N$개의 눈덩이 $(1\le N\le 10^5)$와 $N-1$개의 가지로 이루어진다. 각 가지는 눈덩이 두 개를 잇고, 임의의 두 눈덩이 사이의 경로는 하나뿐이다.

Bessie는 눈덩이 하나에 코를 달았다. 그래서 그 눈덩이가 눈 소의 머리가 된다. 이 눈덩이를 1번 눈덩이라고 한다.

Bessie는 색 염료가 든 양동이를 눈덩이에 뿌려서 조각의 일부를 물들인다. 색은 $1$부터 $10^5$까지의 정수이며, 각 색의 양동이는 무한히 있다. Bessie가 눈덩이 $x$에 색 $c$를 뿌리면, $x$의 서브트리에 있는 모든 눈덩이에도 색 $c$가 입혀진다. 눈덩이 $y$는 $y$에서 1번 눈덩이로 가는 경로 위에 $x$가 있을 때 $x$의 서브트리에 속한다. 한 번 입힌 색은 계속 남는다. 예를 들어 눈덩이에 색 $[1,2,3]$이 있을 때 색 4를 뿌리면, 그 눈덩이의 색은 $[1,2,3,4]$가 된다.

눈덩이 $x$의 색 다양성은 $x$에 입혀진 서로 다른 색의 개수이다. Bessie가 눈덩이 $x$에 대해 물으면, $x$의 서브트리에 있는 모든 눈덩이의 색 다양성 합을 답한다. Bessie가 물을 때마다 이 값을 구하라.

첫 줄에 $N$과 질의의 개수 $Q$ $(1\le Q\le 10^5)$가 주어진다.

다음 $N-1$개 줄에는 눈덩이 $a$와 $b$를 잇는 가지를 나타내는 정수 두 개 $a$, $b$ $(1 \le a, b \le N)$가 주어진다.

마지막 $Q$개 줄에는 질의가 주어진다. 다음 형식의 줄은 Bessie가 눈덩이 $x$에 색 $c$의 염료를 뿌려서 $x$의 서브트리 전체를 물들인다는 뜻이다.

1 x c

다음 형식의 줄은 눈덩이 $x$의 서브트리에 있는 색 다양성의 합을 묻는다.

2 x

여기서 $1\le x\le N$, $1\le c\le 10^5$이다.

종류 2 질의마다, 해당 서브트리의 색 다양성 합을 한 줄에 출력한다. 오버플로를 피하려면 64비트 정수를 써야 한다.

첫 번째 종류 1 질의 후에 눈덩이 4가 색 1로 물든다.

두 번째 종류 1 질의 후에 눈덩이 4와 5가 색 1로 물든다.

세 번째 종류 1 질의 후에 모든 눈덩이가 색 1로 물든다.