Tô Màu Cây

Cho một cây có $N$ nút (gốc ở nút $1$). Có $Q$ thao tác:

• Thao tác 1: 1 x c: Tô màu $c$ cho toàn bộ cây con gốc $x$ (gồm $x$ và tất cả hậu duệ của $x$). Mỗi nút có thể mang nhiều màu khác nhau từ các lần tô khác nhau. Nếu một nút đã mang màu $c$ từ trước thì lần tô này không thêm gì cho nút đó.
• Thao tác 2: 2 x: Đếm tổng số cặp (nút $v$, màu $c$) mà nút $v$ thuộc cây con gốc $x$ và $v$ đang mang màu $c$.

Dữ liệu vào

• Dòng đầu: $N$ và $Q$ ($1\le N,Q\le {10}^5$).
• $N-1$ dòng tiếp theo: mỗi dòng gồm hai số $u,v$ là cạnh nối $u$ và $v$.
• $Q$ dòng tiếp theo: mỗi dòng là một thao tác (dạng 1 x c hoặc 2 x).
  • $1\le x\le N$, $1\le c\le {10}^5$.

Dữ liệu ra

Với mỗi thao tác loại 2, in kết quả trên một dòng.

Ví dụ