Trong một đất nước nọ có ~N~ thành phố được kết nối bởi các đường hàng không ~2~ chiều. Vị chủ tịch kiểm soát không lưu, ông Ronald Krump, thường xuyên thay đổi lịch bay. Cụ thể, mỗi ngày ông ta làm như sau:

• Chọn ~1~ thành phố bất kì,
• Mở các chuyến bay từ thành phố đó đến tất cả các thành phố khác mà các chuyến bay này hiện đang không tồn tại, đồng thời hủy tất cả các chuyến bay hiện có từ thành phố đó.

Ví dụ, nếu từ thành phố ~5~ có các chuyến bay đến thành phố ~1~ và ~2~, nhưng không có chuyến bay đến thành phố ~3~ và ~4~, sau sự thay đổi của Krump, sẽ tồn tại các chuyến bay từ thành phố ~5~ đến thành phố ~3~ và ~4~ và không có chuyến bay đến thành phố ~1~ và ~2~.

Fabian hiếu động tự hỏi rằng, đến một ngày, liệu tất cả các cặp thành phố đều có chuyến bay trực tiếp được hay không và gọi đó là Ngày hoàn hảo. Vì số lượng thành phố khá lớn, Fabian nhờ đến sự trợ giúp của bạn. Hãy viết chương trình xác định xem liệu có tồn tại Ngày hoàn hảo hay không, bất kể động thái của Krump trong mỗi ngày.

Input

Dòng đầu tiên chứa số nguyên ~N~ ~(2 \le N \le 1000)~, số lượng thành phố. Các thành phố được đánh số từ ~1~ đến ~N~.

Dòng thứ hai chứa số nguyên ~M~ ~(0 \le M < \frac{N \cdot (N - 1)}{2})~, số lượng chuyến bay hiện có.

~M~ dòng cuối cùng mỗi dòng chứa hai số nguyên ~x_i~ và ~y_i~ ~(1 \le x_i, y_i \le N,\: x_i \neq y_i)~, chỉ số của hai thành phố hiện đang có chuyến bay trực tiếp.

Output

Nếu tồn tại Ngày hoàn hảo in ra DA (yes trong tiếng Croatia), ngược lại in ra NE (no trong tiếng Croatia).

Sample 1

Input

2
0

Output

DA

Sample 2

Input

3
2
1 2
2 3

Output

NE

Sample 3

Input

4
2
1 3
2 4

Output

DA

Giải thích ví dụ 1: Krump sẽ mở chuyến bay ~1 - 2~ (chuyến bay duy nhất có thể mở).

Giải thích ví dụ 3: Nếu Krump chọn thành phố ~1~, các chuyến bay sẽ tồn tại là ~1 - 2, 1 - 4, 2 - 4~. Sau đó nếu Krump chọn thành phố ~3~, toàn bộ các cặp thành phố sẽ có chuyến bay trực tiếp.