There is a Dictator in Chefland who wants to capture various islands.
He is a very clever person,first he makes a very good plan then he attack the island with his army and capture it.There are N islands in the chefland numbered from 1,2,....N and there is a bidirectional connectivity between some of them.
Plan for attacking the island is:-
They will attack only those island on which after removal of the connections(between any two islands) the graph will have more than one connected components.
- The first line contains an integer T denoting the number of test cases.
- The first line of each test case contains two space-separated integers N, denoting the number of Islands and M, denoting the total number of connections between them.
- M lines follow. Each of the M lines contains two space-separated integers a and b denoting a connection between the islands a and b.
First line of the output will contain the total number of connections and after that You have to print all those bridges (a,b) on removal of which gives more than one connected components.In addition, the list should be sorted in non-decreasing order first by ai and then by bi. Also ai < bi must hold.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 106
- 0 ≤ M ≤ 106
- 1 ≤ a, b ≤ N
1 5 5 1 2 1 3 2 4 2 5
4 1 2 1 3 2 4 2 5
|Time Limit:||0.3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions