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.
• 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$ — 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ụ

Ghi chú

Cây trong ví dụ có cấu trúc: nút 1 nối với 2 và 3; nút 3 nối với 4 và 5.

Sau 1 4 1: cây con gốc 4 (chỉ nút 4) được tô màu 1. Cây con gốc 1 có 1 cặp (nút 4, màu 1).

Sau 1 5 1: cây con gốc 5 (chỉ nút 5) được tô màu 1. Cây con gốc 1 có 2 cặp.

Sau 1 1 1: toàn bộ cây (cây con gốc 1) được tô màu 1. Cây con gốc 1 có 5 cặp (5 nút đều mang màu 1).