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