COCI 2016/2017 - Contest 2 - Burza

View as PDF

Submit solution

Points: 1.50 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 2
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Daniel đã quá mệt với việc tìm việc làm, nên anh ấy quyến định đến thăm nhà của Stjepan, bạn của anh ấy. Khi vào nhà của Stjepan, Daniel đi qua một cây gồm ~N~ đỉnh được đánh số từ ~1~ đến ~N~. Và trên đỉnh ~1~ có đặt một đồng xu.

Stjepan rủ Daniel chơi một trò chơi và bắt anh ấy bịt mắt lại. Daniel quyết định sẽ tham gia trò chơi của người bạn. Luật của trò chơi như sau:

  • Đầu tiên, Daniel chọn một đỉnh bất kì và đánh dấu lên nó.
  • Sau đó, từ đỉnh mà đồng xu đang ở hiện tại, Stjepan sẽ di chuyển đồng xu sang một đỉnh kề chưa được đánh dấu.
  • Cuối cùng, Stjepan đánh dấu vị trí mà đồng xu đã ở trước khi di chuyển.

Ba thao tác trên được xem là một lượt và lặp đi lặp lại cho đến khi Stjepan không thể di chuyển đồng xu đến đỉnh tiếp theo được. Vì Daniel đang bịt mắt nên không có thời điểm nào anh ấy biết được đỉnh nào đang chứa đồng xu. Nhưng anh ấy lại được biết hình dạng của cây và vị trí của đồng xu lúc đầu trò chơi.

Đã hai tiếng kể từ khi anh ấy đến nhà Stjepan và nhận ra mình chưa nộp đơn xin việc vào bất kì công ty nào cả. Daniel chỉ muốn nhanh chóng hoàn thành trò chơi. Giờ anh ấy muốn biết, liệu anh ấy có thể chơi bằng một cách nào đó sao cho dù Stjepan có di chuyển đồng xu ra sao, thì trò chơi cũng kết thúc sau không quá ~K~ lượt chơi. Nói cách khác, trò chơi sẽ kết thúc sau ít hơn ~K~ lần Stjepan di chuyển đồng xu.

Hãy giúp Daniel trả lời câu hỏi trên.

INPUT

  • Dòng đầu gồm hai số nguyên dương, ~N~ và ~K~. ~(1 \le K \le N \le 400)~.
  • Mỗi dòng trong ~N-1~ dòng tiếp theo, gồm hai số nguyên dương ~A~ và ~B~ ~(1 \le A, B \le N)~. Thể hiện có một cạnh vô hướng nối giữa đỉnh ~A~ và đỉnh ~B~.
  • Đề đảm bảo đồ thị được cho là một cây.

OUTPUT

  • Gồm một dòng duy nhất, chứa từ DA nếu câu trả lời là có. Ngược lại chứa từ NE nếu câu trả lời là không.

SAMPLE 1

Input
6 2 
1 2 
2 3 
3 4 
1 5 
5 6
Output
DA

SAMPLE 2

Input
3 1 
1 2 
1 3 
Output
NE
Giải thích ở cho ví dụ thứ hai:

Daniel có thể đánh dấu một nút bất kì. Nếu anh ấy đánh dấu đỉnh ~1~ hoặc ~2~ thì Stjepan vẫn có thể di chuyển đồng xu đến đỉnh ~3~. Và nếu anh ấy đánh dấu đỉnh ~3~, Stjepan có thể di chuyển đồng xu đến đỉnh ~2~.

SAMPLE 3

Input
8 2 
1 2 
2 3 
2 4 
5 6 
6 8 
1 5 
7 1 
Output
DA
Giải thích ở cho ví dụ thứ ba:

Ở lượt đầu tiên, Daniel có thể đánh dấu đỉnh ~2~, và ở lượt thứ hai anh ấy có thể đánh dấu đỉnh ~6~. Dù cho Stjepan có di chuyển đồng xu của anh thấy thế nào ở bước đầu tiên, anh ấy cũng sẽ không thể thực hiện lượt thứ hai được.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.