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 up-gradation 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 un-ordered pair ((1, 2) is the same as (2,1)).
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 a single line contains the number of way that two roads cannot be chosen for upgradation.
- 1 ≤ N ≤ 100,000
- 1 ≤ M ≤ 300,000
- 1 ≤ u, v ≤ N
- u ≠ v
- There is at most one road between any two cities.
Input: 5 6 1 2 2 3 1 3 3 4 4 5 3 5 Output: 6
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).
|Tags||dfs-order, hard, jan14, tuananh93, xor|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.