Cây truy vấn

Trong một chuyến đi nghiên cứu thực vật, FullHouse Dev phát hiện một loài cây đặc biệt với những chiếc đèn phát sáng trên mỗi nhánh. Để hiểu rõ hơn về cách hoạt động của loài cây này, họ đã mô hình hóa nó thành một bài toán.

Bài toán

Một cây là một đồ thị đơn giản trong đó mọi cặp đỉnh đều được kết nối bởi đúng một đường đi. Cho một cây có gốc với \(n\) đỉnh và mỗi đỉnh được gắn một chiếc đèn. Ban đầu, tất cả đèn đều được bật và cây được bắt đầu từ đỉnh \(1\).

Có \(q\) truy vấn thuộc một trong hai loại sau:

1. Chuyển đổi trạng thái đèn tại đỉnh \(v\) (từ Bật sang Tắt hoặc ngược lại)
2. Xác định số đỉnh trong cây con gốc \(v\) mà có thể đi đến được từ \(v\) chỉ qua các đỉnh có đèn đang bật

INPUT FORMAT:

• Dòng đầu tiên: Hai số nguyên \(n\) và \(q\) - số đỉnh và số truy vấn
• \(n-1\) dòng tiếp theo: Hai số \(u\) và \(v\) thể hiện cạnh nối giữa đỉnh \(u\) và \(v\)
• \(q\) dòng tiếp theo: Hai số nguyên \(t\) và \(v\), trong đó \(t\) là loại truy vấn

OUTPUT FORMAT:

• Với mỗi truy vấn loại 2, in ra kết quả trên một dòng

Ràng buộc:

• \(1 \leq n, q \leq 10^5\)

Ví dụ

INPUT

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

OUTPUT

1
2

Giải thích

• Ban đầu tất cả đèn đều bật
• Sau truy vấn đầu tiên, đèn tại đỉnh 3 bị tắt
• Truy vấn thứ hai hỏi về số đỉnh có thể đến được từ đỉnh 2 qua các đỉnh có đèn sáng, kết quả là 1
• Truy vấn thứ ba bật lại đèn tại đỉnh 3
• Truy vấn cuối cùng cho kết quả là 2 vì có thể đi đến cả đỉnh 2 và 3