Подсчёт количества звёзд в графе
Дан неориентированный граф с
v вершинами и e рёбрами. Ваша задача — определить, сколько «звёздных» графов он содержит.Звёздный граф (star graph) — это граф, в котором есть одна центральная вершина, соединённая со всеми остальными вершинами. При этом все остальные вершины связаны только с центральной вершиной и не имеют рёбер друг с другом.
Вход
Первая строка входных данных содержит два целых числа
v (1 ≤ v ≤ 1000) и e (1 ≤ e ≤ 10 000).Следующие
e строк содержат пары целых чисел v1, v2 (1 ≤ v1, v2 ≤ v), задающих ребро между v1 и v2.Выход
Программа должна вывести количество звёздных графов в данном графе.
Примеры
Вход | Выход |
7 6
1 5
2 5
3 5
7 5
6 5
4 5 | 1 |
8 7
1 5
2 5
3 5
7 5
6 5
4 5
1 8 | 0 |
8 6
1 2
2 3
4 2
5 6
7 6
8 6 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB