Cho một cây có \(n\) đỉnh, mỗi đỉnh có thể có màu trắng hoặc đen, ban đầu tất cả các đỉnh là màu trắng. Có \(q\) truy vấn thuộc một trong hai dạng:

• "1 u": Tất cả các đỉnh trên đường đi từ gốc đến \(u\) sẽ trở thành màu đen.
• "2 u": Tất cả các đỉnh trong cây con gốc \(u\) sẽ trở thành màu trắng.

Với mỗi truy vấn, hãy tìm số lượng bị đổi màu sau khi thực hiện xong truy vấn đó.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên \(n,q\).
• \(n-1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u,v\), thể hiện có cạnh nối giữa \(u\) và \(v\).
• \(q\) dòng tiếp theo, mỗi dòng là một truy vấn thuộc định dạng trên.

Dữ liệu ra

• Sau mỗi truy vấn, in ra số lượng đỉnh bị đổi màu.

Điều kiện

• \(1 \le n,q \le 10^5\)
• \(1 \le u,v \le n\)

Input 1

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

Output 1

2
0
2
2