Части многоугольника
(Время: 1 сек. Память: 16 Мб Сложность: 70%)
В правильном n-угольнике провели m диагоналей. Необходимо найти количество связных областей, которые при этом образовались.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа n (3 ≤ n ≤ 40) и m (0 ≤ m ≤ n•(n−3)/2). Каждая из последующих m строк содержит по два числа u и v (1 ≤ u, v ≤ n, min(|u−v|, n−|u−v|) > 1) – номера вершин, соединенных соответствующей диагональю. Вершины нумеруются натуральными числами от 1 до n против часовой стрелки. Каждая диагональ упомянута во входном файле не более одного раза.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 0 | 1 |
| 2 | 4 2
1 3
2 4 | 4 |
| 3 | 5 1
1 3 | 2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
