Bessie's Snow Cow

Snow has arrived on the farm, and as every winter, Bessie is building a snow cow. Usually she tries to make the sculpture look as much like a real cow as possible. This year she wants something more abstract and builds a sculpture shaped like a tree. It consists of $N$ snowballs $(1\le N\le 10^5)$ joined by $N-1$ branches. Each branch connects a pair of snowballs, and there is exactly one path between any two snowballs.

Bessie added a nose to one snowball, which makes it the head of the snow cow. She calls this snowball number 1.

Bessie dyes parts of the sculpture by splashing buckets of colored dye onto snowballs. Colors are integers from $1$ to $10^5$, and she has an unlimited supply of buckets for every color. When Bessie splashes a snowball $x$ with a color $c$, every snowball in the subtree of $x$ also receives color $c$. Snowball $y$ is in the subtree of $x$ when $x$ lies on the path from $y$ to snowball 1. A color stays on a snowball once it is applied. For example, if a snowball has colors $[1,2,3]$ and Bessie splashes it with color 4, the snowball has colors $[1,2,3,4]$.

The colorfulness of snowball $x$ is the number of distinct colors on $x$. When Bessie asks about snowball $x$, the answer is the sum of the colorfulness values of all snowballs in the subtree of $x$. Find these sums at the times Bessie asks.

The first line contains $N$ and the number of queries $Q$ $(1\le Q\le 10^5)$.

Each of the next $N-1$ lines contains two integers $a$ and $b$, a branch between snowballs $a$ and $b$ $(1 \le a, b \le N)$.

Each of the last $Q$ lines is a query. A line of the form

1 x c

means Bessie splashes dye of color $c$ on snowball $x$, coloring every snowball in its subtree. A line of the form

2 x

asks for the sum of colorfulness values in the subtree of snowball $x$. Here $1\le x\le N$ and $1\le c\le 10^5$.

For each query of type 2, print the sum of colorfulness values in the corresponding subtree. Use 64-bit integers to avoid overflow.

After the first type 1 query, snowball 4 is dyed with color 1.

After the second type 1 query, snowballs 4 and 5 are dyed with color 1.

After the third type 1 query, all snowballs are dyed with color 1.