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
parsae: 2019-10-30 08:53:23

can anyone give a test case

scolar_fuad: 2019-09-25 15:00:37

(simpleBridege point problem )

while you save edges u,v as critical point if u>v then keep v,u as critical point then sort the ans in ascending order ... it cost me an hour ...
#happy coding

Last edit: 2019-09-25 15:07:07
rishabh_jiit: 2019-08-29 19:12:15

Print "Caso" not "Case" .Cost me 4WA

moeentm: 2019-08-14 14:47:50

EZZZZZZZZ,AC IN ONE GO,
Thank lord tachanka

shubham97361: 2019-08-07 00:19:58

Xi < Yi must hold.

dishant107: 2019-07-27 16:28:22

In case of TLE, use scanf and printf instead of cin and cout.

surajkumar_cse: 2019-01-17 11:31:16

Here 'c' of Caso is in upper case . It took me around 1 hour to figure out what was going wrong with my code.

dipankar12: 2018-05-19 18:14:49

Time limit very strict for JAVA. Not even one submission.

bradyawn: 2018-01-29 21:44:59

learned new technique: spanish

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

bridges in graph..!!!!


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 C++ 4.3.2 CPP CPP14 CPP14-CLANG JAVA PYTHON PYTHON3