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í.
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