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 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 i ≤ N). In addition, the list should be sorted in non-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

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

hide comments
2023-10-12 11:46:36
There are no multiple edges, so no need to check that.
2022-09-12 18:45:14
AC in one go :)
2022-07-07 19:20:27 David
Impossible AC for java. JVM startup is longer longer than allowed time.
2021-05-19 18:41:13
Take care of the output format.
2021-04-05 10:26:34
Need not check for multiple edges. Just add this step instead inserting directly --> bridge.pb({min(u,it),max(u,it)});
2021-02-01 07:29:18
not take another case like if there is n-1 edges then simply print edges in sorted order
..cost me 2 wa


Last edit: 2021-02-01 07:29:38
2021-01-06 02:17:22
Impossible to AC with raw Python in 0.1s and PyPy is disabled for no reason; downvote.
2020-07-09 09:54:19
showing TLE in JAVA even with fast IO

Last edit: 2020-07-09 09:55:46
2020-07-01 19:02:01
Showing TLE in java while code is O(V+E). Can anyone tell better approach in java
2020-04-11 20:24:06
AC in 1 Go. :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.