Задачі
Колекціонери монет
Колекціонери монет
Програміст Гриша колекціонує монети. У його колекції \textbf{K} різних монет, пронумерованих від \textbf{1} до \textbf{K}. У Гриші є друг Саша, який хоче позичити у Гриші декілька монет. Саша досить вибагливий і монети не стали винятком: є \textbf{N} пар монет, які з естетичних міркувань Саші несумісні одна з одною.
Підскажіть Саші, скількт у нього способів взяти у Гриші \textbf{1}, \textbf{2}, \textbf{3} або \textbf{4} різних монети так, щоб серед взятих монет ніякі дві не були б несумісні.
Наприклад, якщо у Гриші \textbf{3} монети, і Саша вважає несумісними \textbf{2} пари монет: (\textbf{1}, \textbf{2}) і (\textbf{2}, \textbf{3}), то Саша може взяти у Гриші або одну довільну монету (\textbf{3} способи), або дві монети - \textbf{1} і \textbf{3} (довільні інші будуть несумісні). А ось взяти три монети у нього не вийде (серед них опиняться несумісні). Таким чином, у цьому прикладі усього Саша може позичити монети \textbf{4} способами.
\InputFile
Спочатку задано число \textbf{K} (\textbf{1} ≤ \textbf{K} ≤ \textbf{5000}) - кількість монет у Гриші. Припускається, що усі монети Гриші пронумеровано цілими числами від \textbf{1} до \textbf{K}. Потім йде число \textbf{N} (\textbf{0} ≤ \textbf{N} ≤ \textbf{5000}) - кількість несумісних пар. Після нього йде \textbf{N} пар чисел (\textbf{r_1}, \textbf{r_2}), які задають несумісні пари монет. Гарантується, що \textbf{r_1}≠\textbf{r_2} і усі пари різні.
\OutputFile
Виведіть одне число - загальну кількість варіантів у Саші взяти монети у Гриші.
Вхідні дані #1
5 3 1 2 2 3 3 4
Вихідні дані #1
15