Ronald

Υπάρχουν ~N~ πόλεις σε μία χώρα που συνδέονται με αμφίδρομες αεροπορικές συνδέσεις. Ένας τρελός πρόεδρος αεροπορικής εταιρείας, ο Ronald Krump, αλλάζει συχνά το πρόγραμμα πτήσεων. Πιο συγκεκριμένα, καθημερινά κάνει τα εξής:

• επιλέγει μια από τις πόλεις,
• εισάγει πτήσεις από αυτήν την πόλη προς όλες τις άλλες πόλεις όπου αυτές οι πτήσεις δεν υπάρχουν αυτήν τη στιγμή και ταυτόχρονα ακυρώνει όλες τις υπάρχουσες πτήσεις από αυτήν την πόλη

Για παράδειγμα, εάν από την πόλη 5 υπάρχουν πτήσεις προς τις πόλεις 1 και 2, αλλά όχι προς τις πόλεις 3 και 4, μετά την αλλαγή του Krump, θα υπάρχουν πτήσεις από την πόλη 5 προς τις πόλεις 3 και 4, αλλά όχι προς τις πόλεις 1 και 2.

Οι πολίτες αυτής της χώρας αναρωτιούνται αν θα μπορούσε να έρθει μια μέρα που το πρόγραμμα πτήσεων θα είναι ολοκληρωμένο. Με άλλα λόγια, όταν μεταξύ κάθε δύο διαφορετικών πόλεων θα υπάρχει μια (απευθείας) πτήση. Γράψτε ένα πρόγραμμα που, με βάση το τρέχον πρόγραμμα πτήσεων, θα καθορίζει εάν είναι δυνατό να έχουμε μια Ολοκληρωμένη Ημέρα ή αν αυτό δεν θα συμβεί ποτέ, ανεξάρτητα από τις κινήσεις που κάνει ο Krump.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~N\;(2 \le N \le 1\,000)~, τον αριθμό των πόλεων. Οι πόλεις επισημαίνονται με αριθμούς από το 1 έως το ~N~.
Η δεύτερη γραμμή περιέχει τον ακέραιο αριθμό ~M\;(0 \le M < \frac{N \times (N-1)}{2})~, τον αριθμό των τρεχουσών πτήσεων.
Κάθε μία από τις ακόλουθες γραμμές ~M~ περιέχει δύο διαφορετικούς αριθμούς, τις ετικέτες των πόλεων που είναι συνδεδεμένες αυτήν τη στιγμή.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει το DA (στα Κροατικά το "ναι") ή το NE (στα Κροατικά το "όχι").

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

input

2
0

output

DA

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

Στο πρώτο βήμα, ο Krump θα εισαγάγει τη (μόνη δυνατή) γραμμή ~1-2~.

input

3
2
1 2
2 3

output

NE

input

4
2
1 3
2 4

output

DA

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

Εάν ο Krump επιλέξει πρώτα την πόλη 1, θα υπάρχουν οι πτήσεις ~1-2,\;1-4~ και ~2-4~. Εάν στη συνέχεια επιλέξει την πόλη 3, το πρόγραμμα πτήσεων θα γίνει πλήρες.