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 \ne y$, indicando cada arco o arista. Suponed $1 \le n \le 3 \cdot 10^4$, $0 \le m \le 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 \le 10$.

• Test-2:   Entradas donde $n \le 50$.

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

• Test-4:   Entradas de todo tipo.