eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Коллекционеры монет

Коллекционеры монет

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

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

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

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

Входные данные

Сначала вводится число K (1K5000) - количество монет у Гриши. Предполагается, что все монеты Гриши пронумерованы целыми числами от 1 до K. Затем следует число N (0N5000) - количество несовместимых пар. После него идёт N пар чисел (r_1, r_2), задающих несовместимые пары монет. Гарантируется, что r_1r_2 и все пары различные.

Выходные данные

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

Пример

Входные данные #1
5 3
1 2
2 3
3 4
Выходные данные #1
15