Рабочее место участника

Программист Гриша коллекционирует монеты. В его коллекции `K` различных монет, пронумерованных от 1 до K. У Гриши есть друг Саша, который хочет одолжить у Гриши несколько монет. Саша довольно привередлив и монеты не стали исключением: есть `N` пар монет, которые по эстетическим соображениям Саши несовместимы друг с другом.

Подскажите Саше, сколько у него способов взять у Гриши 1, 2, 3 или 4 различных монеты так, чтобы среди взятых монет никакие две не были бы несовместимы.

Например, если у Гриши 3 монеты, и Саша считает несовместимыми 2 пары монет: (1; 2) и (2; 3), то Саша может взять у Гриши либо любую одну монету (3 способа), либо две монеты – 1 и 3 (любые другие будут несовместимы). А вот взять три монеты у него уже не получится (среди них окажутся несовместимые). Таким образом, в этом примере всего Саша может позаимствовать монеты 4 способами.

Сначала вводится число `K` (`1\ ≤\ K\ ≤\ 5000`) – количество монет у Гриши. Предполагается, что все монеты Гриши занумерованы целыми числами от 1 до `K`. Затем следует число `N` (`0\ ≤\ N\ ≤\ 5000`) – количество несовместимых пар. После него идёт N пар чисел (r 1; r 2), задающих несовместимые пары монет. Гарантируется, что `r_1\ ≠\ r_2` и все пары различные.

Выведите одно число – общее количество вариантов у Саши взять монеты у Гриши.

5 3
1 2
2 3
3 4

15

3 2
1 2
2 3

4