Алгоритмы и структуры данных

Подсчёт количества звёзд в графе

Дан неориентированный граф с v вершинами и e рёбрами. Ваша задача — определить, сколько «звёздных» графов он содержит.

Звёздный граф (star graph) — это граф, в котором есть одна центральная вершина, соединённая со всеми остальными вершинами. При этом все остальные вершины связаны только с центральной вершиной и не имеют рёбер друг с другом.

profound.academy-graphs-star-graph.drawio.png

Вход

Первая строка входных данных содержит два целых числа 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

To check your solution you need to sign in
Sign in to continue