Tý có một xâu \(S\) độ dài \(N\). Bạn muốn cắt xâu thành nhiều đoạn liên tiếp sao cho mỗi đoạn là một xâu đối xứng. Hãy tìm số lần cắt ít nhất cần thực hiện.

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

Ràng buộc