Snow Cow Colorful Tree

Bessie has a snow farm! Traditionally, she built realistic snow cows by stacking snowballs, but this year she is inspired by abstract art and wants to create a snow cow in the shape of a tree. The tree comprises \(N\) snowballs (nodes) and \(N-1\) branches (edges) connecting them so that there is a unique path between any two snowballs. Snowball 1 (the cow's head) is specially marked.

Bessie then decorates her snow cow by splashing buckets of paint on some of the snowballs. There are \(10^5\) different paint colors available (numbered from 1 to \(10^5\)), with an infinite supply of each. When Bessie splashes a bucket of paint of color \(c\) on a snowball \(x\), every snowball in the subtree of \(x\) (i.e. every snowball \(y\) such that the unique path from \(y\) to snowball 1 contains \(x\)) gets painted with color \(c\). Even if a snowball already had other colors, the new color is simply added to its palette.

The color richness of a snowball is defined as the number of distinct colors painted on it. Bessie may perform paint operations or ask queries. Each query asks: "What is the sum of the color richness of all snowballs in the subtree of a given snowball \(x\)?"

Your task is to process \(Q\) operations. There are two kinds of operations:

1. Paint operation: 1 x c, which means that Bessie splashes a bucket of paint with color c on snowball x. This colors every snowball in the subtree of x.
2. Query operation: 2 x, asking for the sum of the color richness (i.e. the number of distinct colors) for every snowball in the subtree of x.

Note: The subtree of a snowball \(x\) is defined as all snowballs \(y\) such that \(x\) lies on the unique path from \(y\) to snowball 1.

Help Bessie determine the answers for all query operations.

inputFormat

The first line contains two integers \(N\) and \(Q\) representing the number of snowballs (nodes) and the number of operations, respectively.

The next \(N-1\) lines each contain two integers \(u\) and \(v\) indicating that there is a branch connecting snowball \(u\) and snowball \(v\).

The following \(Q\) lines each represent an operation in one of the following formats:

• 1 x c: A paint operation that applies color c to snowball x (and its entire subtree).
• 2 x: A query operation asking for the sum of color richness in the subtree of snowball x.

outputFormat

For each query operation, output a single integer which is the sum of the color richness (i.e. number of distinct colors) for every snowball in the specified subtree. Each answer should be printed on its own line.

sample

5 4
1 2
1 3
2 4
2 5
1 2 1
2 2
1 1 2
2 2

3
6