Колекціонери монет#3152
Програміст Гріша збирає монети. У нього є колекція з різних монет, пронумерованих від до . Друг Гріші, Саша, хоче позичити кілька монет, але він дуже вибагливий — навіть щодо монет: Саша вважає пар монет несумісними з естетичних міркувань.
Допоможіть Саші визначити, скількома способами він може позичити , , або різні монети у Гріші так, щоб жодні дві взяті монети не були несумісними.
Наприклад, якщо у Гріші є монети, а Саша вважає пари монет несумісними: і , то Саша може взяти будь-яку одну монету ( способи), або пару монет і (оскільки жодна інша пара не годиться через несумісність). Взяти всі три монети неможливо, оскільки така множина містить несумісну пару. У цьому випадку Саша може взяти монети способами.
Перший рядок містить (1 \leq K \leq 5000) — кількість монет у Гріші. Кожна монета має номер від до .
Другий рядок містить (0 \leq N \leq 5000) — кількість несумісних пар.
Далі наведено пар цілих чисел (r_1, r_2), які описують несумісні пари монет. Гарантується, що r_1 \ne r_2 і всі пари різні.
Виведіть одне ціле число — загальну кількість способів, якими Саша може позичити монети у Гріші.
Приклад 1