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
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
meetb_999:
2023-10-12 11:46:36
There are no multiple edges, so no need to check that. |
|
iamdeepanshu:
2022-09-12 18:45:14
AC in one go :) |
|
David:
2022-07-07 19:20:27
Impossible AC for java. JVM startup is longer longer than allowed time. |
|
messier22:
2021-05-19 18:41:13
Take care of the output format. |
|
dineshbarri:
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)}); |
|
ashutosh_coder:
2021-02-01 07:29:18
not take another case like if there is n-1 edges then simply print edges in sorted order
|
|
nadstratosfer:
2021-01-06 02:17:22
Impossible to AC with raw Python in 0.1s and PyPy is disabled for no reason; downvote. |
|
amit_as_king:
2020-07-09 09:54:19
showing TLE in JAVA even with fast IO Last edit: 2020-07-09 09:55:46 |
|
subhash2000:
2020-07-01 19:02:01
Showing TLE in java while code is O(V+E). Can anyone tell better approach in java |
|
abu_rifat:
2020-04-11 20:24:06
AC in 1 Go. :) |
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 |