Algoritmos y Estructuras de Datos

Contar la Cantidad de Estrellas en un Grafo

Dado un grafo no dirigido con v vértices y e aristas, se te pide contar cuántos grafos estrella contiene.

Un grafo estrella es aquel que cuenta con un vértice central conectado a todos los demás vértices, mientras que el resto de vértices solo se conectan al vértice central y no entre sí.

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

Entrada

La primera línea de la entrada contiene dos enteros v (1 ≤ v ≤ 1000) y e (1 ≤ e ≤ 10 000).

Las siguientes e líneas contienen pares de enteros v1, v2 (1 ≤ v1, v2 ≤ v) que representan una arista entre v1 y v2.

Salida

El programa debe imprimir la cantidad de grafos estrella contenidos en el grafo dado.

Ejemplos

Entrada

Salida

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