Counting Two-Hop Forwarding Paths in a Network

A country has a network consisting of several nodes connected by bidirectional links. A very important data packet must be forwarded exactly two times before it reaches its destination. The packet may be generated at any node. In its journey, it will be transmitted along a path of the form \(X \to Y \to Z \to W\), where \(Y\) and \(Z\) are the two nodes that forward the packet. Note that:

• The communication is over undirected links but the forwarding process is directional.
• The source \(X\) and destination \(W\) may be the same.
• The two intermediate nodes (i.e. \(Y\) and \(Z\)) must be distinct and, in addition, neither of them can be equal to the source or destination. That is, \(Y\) \(\neq\) \(Z\), \(Y \neq X, W\) and \(Z \neq X, W\).

Given the network description, you are to count the total number of valid forwarding paths.

The mathematical expression for the count is as follows. For every directed link that can serve as the middle hop from \(Y\) to \(Z\) (each undirected edge contributes two directed edges), the number of valid completions of the path is:

[ (\deg(Y)-1)\times(\deg(Z)-1), ]

where \(\deg(V)\) denotes the degree of node \(V\) (i.e. the number of nodes connected to \(V\)). Summing this over every directed edge gives the final answer.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) (the number of nodes and the number of edges, respectively). Each of the next \(m\) lines contains two integers \(u\) and \(v\), indicating that there is a bidirectional link between nodes \(u\) and \(v\). Nodes are numbered from 1 to \(n\).

outputFormat

Output a single integer, the total number of valid forwarding paths.

sample

3 3
1 2
2 3
3 1

6