TOMAU Tô màu cho cây

Cho đồ thị dạng cây gồm N đỉnh, N – 1 cạnh, có đỉnh 1 là gốc của cây.

Nhánh con gốc x bao gồm đỉnh x và các đỉnh mà đường đi từ đỉnh gốc 1 đến nó phải đi qua đỉnh x.

Thực hiện tô màu lên các đỉnh, mỗi màu là 1 số nguyên c, một đỉnh có thể được tô màu nhiều lần và mang nhiều màu khác nhau. Ví dụ, đỉnh 2 đang mang các màu [1, 2, 3], nếu ta tô thêm màu 4 cho đỉnh 2 thì nó sẽ có 4 màu [1, 2, 3, 4].

Trọng số của đỉnh là số màu khác nhau mà đỉnh đó được tô. Trọng số của nhánh con là tổng trọng số của các đỉnh thuộc nhánh con.

Thực hiện Q truy vấn thuộc 1 trong 2 loại sau:

            1 x c : tô thêm màu c cho toàn bộ các đỉnh thuộc nhánh con gốc x

            2 x    : tính tổng trọng số của nhánh con gốc x.

Yêu cầu: cho biết kết quả của mỗi truy vấn loại 2.

Input

• Dòng đầu ghi 2 số N Q (1 ≤ N ≤ 10⁵; 1 ≤ Q ≤ 10⁵)
• N – 1 dòng tiếp theo, mỗi dòng ghi 2 số  a b, cho biết có cạnh nối giữa 2 đỉnh a, b ((1 ≤ a,b ≤ N)
• Q dòng tiếp theo, mỗi dòng ghi 1 truy vấn loại 1 x c hoặc 2 x. (1 ≤ x ≤ N; 1 ≤ c ≤ 10⁵)

Output: Mỗi dòng ghi kết quả của 1 truy vấn loại 2.

Input	Output
5 10 1 2 1 3 3 4 3 5 1 4 1 2 1 2 4 2 5 1 5 3 2 1 2 5 1 1 2 2 1 2 2	1 1 0 2 1 7 1