EC_P - Critical Edges


This time I will not bore you with a long and boring sentence. Give a connected graph, you must find all the edges that are critical, in other words you must find the edges which when removed divide the graph.

Input

 

The first line contains a NC (1 ≤ NC ≤ 200), the number of test cases integer. Then follow NC test cases.
Each case begins with two integers N (1 ≤ N ≤ 700) and M (N-1 ≤ M ≤ N * (N-1) / 2), the number of locations and number of roads respectively. Then follow M lines, each with a pair of integers b (1 ≤ a, b ≤ N) indicate that between the city and b there is a way.

The first line contains a integer NC (1 ≤ NC ≤ 200), the number of test cases. Then follow NC test cases.

Each case begins with two integers N (1 ≤ N ≤ 700) and M (N-1 ≤ M ≤ N * (N-1) / 2), the number of nodes and the number of edges respectively. Then follow M lines, each with a pair of integers a b (1 ≤ a, b ≤ N) indicate that between the node a and the node b there is a edge.

Output

For each test case print the list of ways to protect the following format:

Caso # <n>

<t>

<x1> <y2>

<x2> <y2>

...

<xt> <yt>

Where n is the case number (starting from 1), t is the total of critical edges, list elements xi  yi indicates, for each line, there is a critical edge between the node xi and node yi (1 ≤ xi <yi ≤ N). In addition, the list should be sorted in no-decreasing order first by xi and then by yi. Also xi < yi must hold.

If there isn't any critical edge print: "Sin bloqueos" (quotes for clarity).

Example

Input:
3

5 4
1 2
4 2
2 3
4 5

5 5
1 2
1 3
3 2
3 4
5 4

4 6
1 3
1 4
2 1
3 2
4 2
4 3
Output:
Caso #1
4
1 2
2 3
2 4
4 5
Caso #2
2
3 4
4 5
Caso #3
Sin bloqueos

hide comments
aman_9899: 2017-06-14 23:32:55

bridges in graph..!!!!

Liquid_Science: 2016-08-01 12:09:53

Very hard time limit for java :(
Can this be done faster than O(V+E) ?

Last edit: 2016-08-02 16:13:43
aspro: 2016-06-03 18:42:57

good quetion....learned new concept....take care of o/p format

bruzelee: 2016-05-04 23:55:34

while saving the vector of pairs(saving the bridge edges in a data structure ) as u,v make sure you save u the minimum one out of two and v as the max one out of the two then apply the sorting algo and then print the ordered pair

varun yadav: 2016-01-29 21:53:02

Thx @Eddy Cael

Pranay: 2014-03-01 02:09:41

@Eddy : Could you please check why WA for id 11149094 ? Thanks.


Added by:Eddy Cael
Date:2013-10-31
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C-CLANG C CPP C++ 4.3.2 CPP14-CLANG CPP14 JAVA PYTHON PYTHON3