Special Edge :
Difficulty Level : Medium
Submissions : 821
Asked In :
Marks :50
: 23 | : 0
You are given a connected undirected graph having $$$N$$$ nodes numbered from $$$1$$$ to $$$N$$$ and $$$M$$$ edges between its nodes. It is guaranteed that the input graph is connected and consists of no self loops and no multiple edges between two vertices. Edges are given in the form of $$$u, v$$$.
An edge is special if, when removed, the number of connected components in the graph increases.
Determine the number of unordered pairs of nodes $$$(u, v)$$$ such that each and every simple path (path with no edges repeated) between node $$$u$$$ and node $$$v$$$ consists of exactly 1 special edge.
The first line of input consists of 2 space separated integers $$$-$$$ $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 2$$$ x $$$10^5)$$$ where $$$n$$$ is the total number of nodes and $$$m$$$ is the number of edges in the graph. Then, each of the next $$$m$$$ lines consists of 2 space separated integers $$$-$$$ $$$u$$$ and $$$v$$$, which denotes that there is an edge between the nodes $$$u$$$ and $$$v$$$.
The output should consist of a single integer $$$-$$$ the total number of such pairs.
4 4 1 2 2 3 3 4 2 4
3
8 8 1 2 2 3 3 4 4 1 1 5 2 6 3 7 4 8
16
$$$m \geq n-1$$$
