Counting The Important Pairs

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
[a simple graph is an undirected graph that has no loops (edges connected at both ends to the same vertex) and no more than one edge between any two different vertices.]
Retrieved from http://en.wikipedia.org/wiki/Graph_(mathematics)
The road system at Byteland can be seen as a simple graph in which the vertices represented by the cities and the edges represented by the roads connected two different cities. Besides, the road system is connected it means people can travel between any two cities. It is decided by the president that two roads will be concurrently upgraded in the next month. Since it may take a couple of weeks to get the work done, two roads should be chosen so that the connectivity of the system is hold during the upgradation process. More clearly, people still can go between any pair of cities without using that two roads.
Which roads should be upgraded is not decided yet. There may be no way to choose such a two roads or may be many ways. Your mission is counting how many pair of roads cannot be chosen. Notice that two roads must be different and we consider only unordered pair ((1, 2) is the same as (2,1)).
Input
The first line of the input contains two integers N M which are the number of cities and roads respectively. Each line in the next M contains two integers u v which means there is a road connects the uth city to the vth city.
Output
Output a single line contains the number of way that two roads cannot be chosen for upgradation.
Constraints
 1 ≤ N ≤ 100,000
 1 ≤ M ≤ 300,000
 1 ≤ u, v ≤ N
 u ≠ v
 There is at most one road between any two cities.
Example
Input: 5 6 1 2 2 3 1 3 3 4 4 5 3 5 Output: 6
Explanation
There are 5 cities and 6 roads (numbered from 1 to 6). There are 6 pairs of roads cannot be chosen which are (1, 2), (1, 3), (2, 3), (4, 5), (4, 6) and (5, 6).
Author:  tuananh93 
Editorial  http://discuss.codechef.com/problems/TAPAIR 
Tags  dfsorder, hard, jan14, tuananh93, xor 
Date Added:  15052013 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 