Problems
Коллекционеры монет
Коллекционеры монет
Программист Гриша коллекционирует монеты. В его коллекции \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
Выведите одно число - общее число вариантов у Саши взять монеты у Гриши.
Input example #1
5 3 1 2 2 3 3 4
Output example #1
15