Time limit: 1.0s , Memory limit: 256M , Points: 1
Cho cây gồm đỉnh được đánh số từ đến , mỗi đỉnh được tô màu đen hoặc trắng. Cho danh sách đỉnh được tô màu đen, các đỉnh còn lại được tô màu trắng.
Cây được gọi là con của cây nếu cây thu được bằng cách xóa đi một vài đỉnh và cạnh của cây . Kích thước của một cây được định nghĩa là số đỉnh cây đó. Bạn hãy xác định kích thước nhỏ nhất của cây con chứa tất cả các đỉnh được tô màu đen.
Input
- Dòng đầu tiên chứa hai số nguyên và .
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và mô tả các cạnh của cây .
- Dòng cuối cùng chứa số nguyên .
- Dữ liệu đảm bảo các cạnh đã cho tạo thành một cây hợp lệ.
Output
- In ra kích thước nhỏ nhất của cây thỏa mãn điều kiện.
Examples
Sample Input 1
7 3
6 3
5 2
1 2
3 7
2 4
1 3
3 5 1
Sample Output 1
4
Sample Input 2
3 3
1 2
1 3
1 2 3
Sample Output 2
3
Notes
Trong ví dụ đầu tiên, cây và cây con nhỏ nhất được mô tả như trong hình sau:
Comments