Thuở xa xưa, vương quốc Li Đốn Quê là một vương quốc hùng mạnh nằm gần bán đảo Tra Sờn. Sử sách ghi lại rằng vương quốc Li Đốn Quê được chia làm \(n\) ngôi làng nhỏ. Để thuận tiện cho việc quản lý, quốc vương đánh số các ngôi làng từ \(1\) đến \(n\). Các nhà sử học cũng tìm được một tấm bản đồ cổ và biết được rằng, \(n\) ngôi làng này được kết nối với nhau bởi \(n - 1\) con đường đất. Tất nhiên, mọi con đường đều là hai chiều và chúng đảm bảo rằng người dân có thể đi từ một ngôi làng bất kỳ tới tất cả các ngôi làng còn lại, thông qua một hoặc nhiều con đường.

Nhằm củng cố khả năng phòng thủ và đảm bảo quân đội luôn sẵn sàng trước các mối đe dọa từ ngoại bang, nhà vua tiến hành diễn tập chiến lược với \(q\) tình huống xâm lăng giả định. Các tình huống được đánh số từ \(1\) tới \(q\), và trong tình huống thứ \(j\), giả định rằng các ngôi làng có chỉ số từ \(l_j\) đến \(r_j\) đồng loạt bị tấn công bởi các thế lực ngoại xâm.

Để ứng phó, nhà vua phải tìm cách huy động quân đội đến các ngôi làng bị tấn công càng nhanh càng tốt. Đồng thời, việc di chuyển quân giữa các ngôi làng này cũng phải thuận tiện để các ngôi làng có thể hỗ trợ và bảo vệ lẫn nhau. Do đó, nhà vua cần xác định một vùng báo động chiến tranh. Vùng này sẽ bao gồm một số ngôi làng, đảm bảo được hai yếu tố. Thứ nhất, tất cả các ngôi làng bị tấn công đều phải nằm trong vùng báo động chiến tranh. Thứ hai, vùng báo động chiến tranh phải là một vùng liên thông, có nghĩa là nếu có hai ngôi làng cùng nằm trong vùng báo động chiến tranh, luôn tồn tại một cách di chuyển giữa hai ngôi làng này mà chỉ đi qua các ngôi làng thuộc vùng báo động chiến tranh.

Việc thiết lập chế độ thời chiến là điều nhà vua không hề mong muốn, bởi điều này gây ảnh hưởng tới đời sống sinh hoạt và sản xuất của người dân. Do đó, nhà vua luôn muốn số ngôi làng nằm trong vùng báo động chiến tranh là nhỏ nhất có thể.

Các bạn hãy giúp quốc vương xác định, với mỗi kế hoạch giả định, số ngôi làng tối thiểu nằm trong vùng báo động chiến tranh.

Dữ liệu

Vào từ file văn bản kingdom.inp:

• Dòng thứ nhất chứa hai số nguyên \(n\) và \(q\) \((1 \le n, q \le 50^3)\).
• Trong \(n - 1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(u_i\) và \(v_i\) \((1 \leq u_i, v_i \leq n)\) cho biết có một con đường đất kết nối hai ngôi làng \(u_i\) và \(v_i\).
• Trong \(q\) dòng cuối cùng, dòng thứ \(j\) chứa hai số nguyên \(l_j\) và \(r_j\) \((1 \leq l_j \leq r_j \leq n)\) mô tả tình huống giả định thứ \(j\).

Kết quả

Ghi ra file văn bản kingdom.out:

• Gồm \(q\) dòng, dòng thứ \(j\) chứa một số nguyên là số ngôi làng tối thiểu thuộc vùng báo động chiến tranh trong tình huống giả định thứ \(j\).

Ràng buộc

• Subtask \(1\) (\(11\) điểm): \(n, q \leq 500\)
• Subtask \(2\) (\(11\) điểm): \(n, q \leq 2000\)
• Subtask \(3\) (\(17\) điểm): \(n \leq 2000\)
• Subtask \(4\) (\(19\) điểm): Mỗi ngôi làng có tối đa \(2\) con đường nối trực tiếp với các ngôi làng khác.
• Subtask \(5\) (\(23\) điểm): Tổng giá trị \(r_j - l_j\) trong các tình huống giả định không quá \(5 \cdot 10^5\).
• Subtask \(6\) (\(19\) điểm): Không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

kingdom.inp

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

kingdom.out

4
2
3

Giải thích

Hình dưới đây mô tả các con đường ở vương quốc Li Đốn Quê trong ví dụ trên:

Ta có \(q = 3\) tình huống giả định như sau:

• \(l_1 = 1, r_1 = 3\): vùng báo động chiến tranh chứa các ngôi làng \(\{ 1, 2, 3, 4\}\).
• \(l_2 = 3, r_2 = 4\): vùng báo động chiến tranh chứa các ngôi làng \(\{ 3, 4\}\).
• \(l_3 = 4, r_3 = 5\): vùng báo động chiến tranh chứa các ngôi làng \(\{ 2, 4, 5\}\).