Tại Byteotia có $n$ thành phố, được đánh số từ $1$ đến $n$, và $n-1$ con đường, mỗi con đường nối trực tiếp hai thành phố. Từ mọi thành phố, ta có thể đi đến mọi thành phố khác theo đúng một cách duy nhất mà không cần quay lại.
Bạn đang phụ trách cơ quan phản gián Byteotia. Bạn vừa nhận được thông tin rằng các điệp viên từ Bitotia thù địch đã xâm nhập vào một số thành phố! Bạn biết rằng các điệp viên Bitotia luôn hoạt động theo cặp. Khi một điệp viên trong cặp tìm thấy thông tin hữu ích, họ sẽ cố gắng đi đến thành phố nơi điệp viên thứ hai đang ở để chia sẻ những gì tìm được. Đối với mỗi cặp trong số $q$ cặp điệp viên, bạn biết chính xác các thành phố mà các điệp viên trong cặp đó hiện đang ở.
Nhiệm vụ của bạn là đảm bảo không có cặp điệp viên nào có thể gặp nhau. Để đạt được điều này, bạn có thể tuyên bố cách ly bất kỳ tập hợp thành phố nào. Việc đi vào, đi qua hoặc rời khỏi một thành phố đang bị cách ly đều bị cấm.
Các điệp viên tạo thành một cặp có thể gặp nhau khi và chỉ khi tồn tại một dãy các thành phố $x_1, x_2, \dots, x_k$, không có thành phố nào trong số đó bị cách ly, sao cho $x_1$ là thành phố nơi một điệp viên đang ở, $x_k$ là thành phố nơi điệp viên kia đang ở, và với mọi $1 \le i \le k-1$, các thành phố $x_i$ và $x_{i+1}$ được nối trực tiếp bởi một con đường.
Tất nhiên, bạn không muốn làm tê liệt cả đất nước, vì vậy bạn muốn đặt càng ít thành phố vào diện cách ly càng tốt. Nhiệm vụ của bạn là tính toán số lượng thành phố tối thiểu phải cách ly để ngăn chặn mọi cặp điệp viên gặp nhau. Ngoài ra, bạn phải cung cấp bất kỳ danh sách ngắn nhất nào gồm các thành phố cần cách ly để đạt được mục tiêu này.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $q$ ($2 \le n \le 5 \cdot 10^5$, $1 \le q \le 5 \cdot 10^5$), lần lượt là số lượng thành phố tại Byteotia và số lượng cặp điệp viên.
$n-1$ dòng tiếp theo chứa mô tả các con đường. Dòng thứ $i$ (với $1 \le i \le n-1$) chứa hai số nguyên $a_i$ và $b_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$), nghĩa là thành phố $a_i$ và $b_i$ được nối trực tiếp bởi một con đường.
$q$ dòng tiếp theo chứa mô tả các cặp điệp viên. Dòng thứ $i$ (với $1 \le i \le q$) chứa hai số nguyên $c_i$ và $d_i$ ($1 \le c_i, d_i \le n$, $c_i \neq d_i$), đại diện cho các thành phố nơi cặp điệp viên thứ $i$ đang ở (một người ở thành phố $c_i$, người kia ở thành phố $d_i$). Nhiều điệp viên (từ các cặp khác nhau) có thể ở cùng một thành phố.
Dữ liệu ra
Dòng đầu tiên của dữ liệu ra nên chứa một số nguyên $s$, đại diện cho số lượng thành phố tối thiểu phải cách ly để ngăn chặn mọi cặp điệp viên gặp nhau. Dòng thứ hai nên chứa $s$ số nguyên đại diện cho các thành phố cần phải cách ly để đạt được điều này.
Ví dụ
Dữ liệu vào 1
7 3 1 2 1 3 2 4 2 5 2 6 3 7 1 5 1 6 3 7
Dữ liệu ra 1
2 2 3
Ghi chú
Có ba cặp điệp viên, được ký hiệu trong hình bằng các chữ cái $A$, $B$, và $C$. Nếu các thành phố $2$ và $3$ (được đánh dấu bằng các vòng tròn) bị cách ly, không cặp điệp viên nào có thể gặp nhau mà không đi qua một trong các thành phố này. Các danh sách thành phố hợp lệ khác để cách ly bao gồm, ví dụ, $1$ và $3$, hoặc $1$ và $7$.
Hình minh họa: Một cây với 7 nút, các cặp điệp viên được đánh dấu trên các đường đi tương ứng.
Nhiệm vụ con
| Nhiệm vụ con | Giới hạn | Điểm |
|---|---|---|
| 1 | $n, q \le 20$ | 9 |
| 2 | $q \le 2$ | 11 |
| 3 | Mỗi đường đi nối một cặp điệp viên giao với tối đa một đường đi khác | 17 |
| 4 | $a_i = i, b_i = i + 1$ với $1 \le i \le n - 1$ | 12 |
| 5 | $a_i = i + 1, b_i = \lfloor \frac{i+1}{2} \rfloor$ với $1 \le i \le n - 1$ | 23 |
| 6 | Không có giới hạn bổ sung | 21 |
Nếu chỉ dòng đầu tiên trong câu trả lời của bạn là đúng, lời giải của bạn sẽ nhận được 80% số điểm cho bài kiểm tra đó. Bạn không cần phải xuất ra dòng thứ hai để nhận được số điểm này.