Roads in Shinjuku
All submissions for this problem are available.
The government of Britannia wants to know some statistics about the city of Shinjuku. They wanted to count the number of unordered pairs of intersections S and T in the city such that there are at least two edge disjoint paths between them.
First line of the test case contains N and M the number of intersections in Shinjuku and the total number of connections. The next M lines contain two integers i and j indicating a single connection between intersections i and j.
It is guaranteed that no connection occurs twice in the input and there is no connection between the same intersection.
Output on a single line, the number of unordered pairs of intersections S and T, S != T such that there are atleast two edge disjoint paths between S and T.
- 1 ≤ N,M ≤ 105
Input: 4 4 1 2 2 3 1 3 3 4 Output: 3
The three pairs of nodes are (1,2), (1,3) and (2,3)
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, LISP sbcl, LISP clisp, SCM guile, ERL, TCL, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions