Conexiones en un grafo P32618

Dado un grafo con n vértices, calculad cuántos subconjuntos de dos vértices x e y son tales que hay algún camino desde x hasta y, y también algún camino desde y hasta x.

Tened en cuenta que el grafo dado puede ser dirigido o no dirigido. En el primer caso una conexión directa entre x e y consiste en un arco dirigido desde x hasta y, mientras que en el segundo caso consiste en una arista bidireccional que conecta x e y en ambos sentidos.

Entrada

La entrada consiste en diversos casos, cada uno con un carácter ‘D’ o ‘N’ que indica si el grafo es dirigido o no, seguido de n, seguida del número de arcos o aristas m. Siguen m pares de vértices x y, con x ≠ y, indicando cada arco o arista. Suponed 1 ≤ n ≤ 3 · 10⁴, 0 ≤ m ≤ 5n, que los vértices se numeran a partir de 0, y que no hay arcos o aristas repetidos.

Salida

Para cada caso, escribid el número de subconjuntos de dos vértices mutuamente accesibles entre sí.

Puntuación

• Test-1:   Entradas donde n ≤ 10.  10 Puntos 

• Test-2:   Entradas donde n ≤ 50.  20 Puntos 

• Test-3:   Entradas sólo con grafos no dirigidos.  20 Puntos 

• Test-4:   Entradas de todo tipo.  50 Puntos