Burza

Ο Daniel έχει βαρεθεί να ψάχνει για δουλειά, κι έτσι αποφάσισε να επισκεφτεί τον φίλο του Stjepan. Παραδόξως, όταν μπήκε στο σπίτι του Stjepan, συνάντησε ένα δέντρο με ~N~ κόμβους που συμβολίζονται με αριθμούς από το ~1~ έως το ~N~. Ο κόμβος με αριθμό 1 περιέχει ένα νόμισμα.

Ο Stjepan του είπε: "Δέσε τα μάτια και θα παίξουμε!" Ο Daniel του έριξε μια περίεργη ματιά, αλλά αποφάσισε να το κάνει. Ο Stjepan του είπε τότε τους κανόνες του παιχνιδιού:

• Ο Daniel διαλέγει έναν κόμβο και τον σημειώνει
• Ο Stjepan μετακινεί το κέρμα σε έναν χωρίς σήμανση κόμβο δίπλα σε αυτόν στον οποίο βρίσκεται αυτήν τη στιγμή το νόμισμα
• Ο Stjepan σηματοδοτεί τον κόμβο από τον οποίο μετέφερε το νόμισμα

Αυτά τα τρία βήματα επαναλαμβάνονται έως ότου ο Stjepan δεν μπορεί να κάνει άλλη κίνηση. Δεδομένου του γεγονότος ότι έχει δεμένα τα μάτια, ο Daniel δεν ξέρει ακριβώς ποιος κόμβος περιέχει το νόμισμα σε οποιαδήποτε δεδομένη στιγμή του παιχνιδιού. Ωστόσο, γνωρίζει το περίγραμμα του δέντρου και πού ήταν το νόμισμα στην αρχή του παιχνιδιού.

Ο Daniel μόλις συνειδητοποίησε ότι δεν έχει κάνει αίτηση για μια δουλειά τις τελευταίες δύο ώρες και θέλει να τελειώσει γρήγορα το παιχνίδι. Τώρα θέλει να μάθει αν μπορεί να παίξει με τρόπο που, όποιες κινήσεις κι αν κάνει ο Stjepan, το παιχνίδι τελειώνει σε το πολύ k κινήσεις. Με άλλα λόγια, έτσι ώστε ο Stjepan να μετακινεί το νόμισμα λιγότερες από k φορές.

Βοηθήστε τον Daniel και καθορίστε εάν μπορεί να ολοκληρώσει το παιχνίδι στην ώρα του και να επιστρέψει στην αποστολή του βιογραφικού του σε εταιρείες που δεν έχει ακούσει ποτέ.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο ακέραιους, ~N~ και ~K\;(1 \le K \le N \le 400)~.
Καθεμία από τις ακόλουθες ~N - 1~ γραμμές περιέχουν δύο ακέραιους αριθμούς ~A~ και ~B~ ~(1 \le A, B \le N)~ που δηλώνουν ότι υπάρχει ένας μη κατευθυνόμενος σύνδεσμος μεταξύ κόμβων που επισημαίνονται με ~A~ και ~B~. Είναι εγγυημένο ότι το δεδομένο γράφημα θα είναι δέντρο.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τη λέξη "DA" (στα Κροατικά το "ΝΑΙ"), χωρίς εισαγωγικά, εάν ο Daniel μπορεί να διασφαλίσει ότι το παιχνίδι τελειώνει με το πολύ ~K~ κινήσεις, και "NE" (στα Κροατικά το "ΌΧΙ") εάν δεν μπορεί.

Παραδείγματα

input

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

output

DA

input

3 1
1 2
1 3

output

NE

Επεξήγηση του 2ου παραδείγματος:

Ο Daniel μπορεί να σημαδέψει οποιονδήποτε κόμβο. Εάν σημαδέψει τον κόμβο 1 ή 2, ο Stjepan μπορεί να μετακινήσει το κέρμα στον κόμβο 3 και εάν σημειώσει τον κόμβο 3, ο Stjepan μπορεί να μετακινήσει το κέρμα στον κόμβο 2.

input

8 2
1 2
2 3
2 4
5 6
6 8
1 5
7 1

output

DA

Επεξήγηση του 3ου παραδείγματος:

Στην πρώτη του κίνηση, ο Daniel μπορεί να σημειώσει τον κόμβο 2 και στη δεύτερη κίνηση τον κόμβο 6. Όπου ο Stjepan μετακινήσει το κέρμα στην πρώτη του κίνηση, δεν θα μπορεί να κάνει δεύτερη κίνηση.