В этом году на кружок по олимпиадному программированию в вашей школе записалось на удивление много учеников – целых $$$2n$$$ человек. Для более продуктивной работы их нужно разбить на две учебные группы по $$$n$$$ человек. Однако не все школьники в кружке ладят друг с другом, и некоторые категорически не хотят оказаться в одной группе.
В качестве первой задачи на кружке вас попросили написать программу, определяющую количество способов разбить всех $$$2n$$$ учеников на две равные группы так, чтобы в каждой группе не оказалось ни одной пары враждующих школьников. Поскольку это количество может быть большим, вам нужно вычислить его по модулю $$$10^9 + 7$$$.
Первая строка содержит два целых числа: $$$n$$$ и $$$m$$$ $$$(1 \le n \le 10^3, 0 \le m \le 10^5)$$$ – количество школьников в каждой группе и количество пар враждующих школьников соответственно.
Далее следуют $$$m$$$ строк, каждая из которых содержит два числа $$$a_i, b_i$$$ $$$(1 \le a_i, b_i \le 2 n)$$$ – номера школьников, между которыми есть вражда.
Выведите количество способов разбить школьников на две учебные группы размера $$$n$$$ по модулю $$$10^9 + 7$$$. Если ни одного корректного разбиения не существует, выведите 0.
Два разбиения, отличающиеся лишь порядком групп, не считаются различными.
4 41 21 63 55 8
3
2 41 22 33 11 4
0
В первом примере возможны следующие разбиения: (1, 3, 4, 8) (2, 5, 6, 7), (1, 3, 7, 8) (2, 4, 5, 6) и (1, 4, 5, 7) (2, 3, 6, 8).
| Финал ВКОШП.Junior 2025 |
|---|
| Закончено |
