Недавно в коде FOS обнаружили серьезный баг. Глава компании F хочет найти виновника бага и наказать его. Для этих целей было организовано собрание, центральным вопросом которого был: кто сделал баг? На собрании каждый из n программистов сказал: «Я точно знаю, что баг сделал либо x, либо y!»
Глава компании решил выбрать двух подозреваемых и вызвать их в свой кабинет. Конечно, он должен учитывать мнения программистов. Поэтому глава хочет сделать выбор так, чтобы с ним были согласны как минимум p программистов из n. Программист согласен с выбором двух подозреваемых, если хотя бы одного из двух людей, на которых он указывал на собрании, выбрали в качестве подозреваемого. Сколькими способами глава F может выбрать двух подозреваемых?
Обратите внимание, что даже если какого-то программиста выбрали в качестве подозреваемого, он может быть согласен с выбором главы (если он указывал на собрании на другого выбранного подозреваемого).
В первой строке записаны целые числа n и p (3 ≤ n ≤ 3·105; 0 ≤ p ≤ n) — количество программистов компании F и минимальное требуемое число согласных.
В каждой из n следующих строк записаны два целых числа xi, yi (1 ≤ xi, yi ≤ n) — номера программистов из высказывания i-го программиста. Гарантируется, что xi ≠ i, yi ≠ i, xi ≠ yi.
Выведите единственное целое число — количество возможных выборов. Обратите внимание, что порядок подозреваемых не имеет значения, то есть выборы (1, 2) и (2, 1) считаются одинаковыми.
4 2
2 3
1 4
1 4
2 1
6
8 6
5 6
5 7
5 8
6 2
2 1
7 3
1 3
1 4
1
Название |
---|