Red Social Patito

Time Limit:
1 Sec
Memory Limit:
128Mb
Enviados:
176
Resuelto:
52

Descripción

La Red social "Patito" es un sitio donde puedes interactuar con tus amigos de la carrera, o esa era la idea. Muchas personas no solo agregan a sus amigos reales como contactos, sino que agregan a personas con las que tal vez jamás hablaron. La realidad es que si las personas A y B son amigos y las personas B y C también son amigos, las personas A y C no necesariamente deben ser amigos. En la red social se ve otro comportamiento.
En general notaste dos reglas:

Si A es amigo real de B, entonces A agregará como contacto a B (al igual que haría B).

Si A es contacto de B y B es contacto de C entonces A agregara a C como su contacto (al igual que haría C).

Todo esto se puede modelar como dos grafos, uno que considera relaciones de amistad real (al cual llamaremos grafo de amistad) y el otro grafo que considera amistad en la red social patito (al cual llamaremos grafo patito).

Entrada

La primera línea de entrada tiene dos enteros positivos N y M que son el número de nodos y de arcos en el grafo de amistad. Las siguientes M líneas contienen dos pares de enteros U y V que indican una relación de amistad entre los usuarios U y V.

N,M<=100

0<=U,V<=N-1

Salida

Imprimir la cantidad de arcos en total que tiene el grafo patito.

Ejemplo Entrada

Copy icon
5 4
0 1
2 3
4 2
1 2

Ejemplo Salida

Copy icon
8

Ayuda