Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AI_BLO - Bloquera

En cierto país existe una población llamada Bloquera que nunca está contenta con ninguna cosa que le da el Gobierno; ella tiene una manera muy peculiar de exigir sus pedidos: ¡bloqueando carreteras! No obstante, tiene muy pocos habitantes y entre todos pueden bloquear solamente un camino.

El país cuenta con un sistema de carreteras tal que es posible ir desde cualquier población a otra de al menos una manera, y los ciudadanos de Bloquera solo llamaran la atención del Gobierno si logran bloquear un camino que divida al país en 2 grupos incomunicados.

Debido a que el estado no puede permitirse una situación tan perjudicial, se decidió reforzar la seguridad en las carreteras enviando protección militar. Las autoridades ahora se están preguntando: ¿cuáles son los caminos que se necesitan proteger?

Input

La primera linea contiene un entero NC (1 ≤ NC ≤ 200), el número de casos de prueba. A continuación siguen NC casos de prueba.

Cada caso comienza con dos enteros N (1 ≤ N ≤ 700) y M (N-1MN*(N-1)/2 ), la cantidad de poblaciones y el número de carreteras respectivamente. A continuación siguen M lineas, cada una con un par de enteros a b (1 ≤ a, b ≤ N) que indican que entre la ciudad a y b existe un camino.

Output

Para cada caso de prueba imprimir la lista de caminos a proteger con el siguiente formato:

Caso #<n>
<t>
<x1> <y2>
<x2> <y2>
...
<xt> <yt>
 

donde n es el número de caso (empezando desde 1), t es el total de carreteras a resguardar y la lista de t elementos xi yi indica, por cada linea, que se debe proteger el camino entre la ciudad xi y la ciudad yi (1 ≤ xi < yi ≤ yi). Además, la lista debe estar ordenada en forma no decreciente primero por xi y luego por yi.

En caso de que no sea necesario resguardar ningún camino imprimir: "Sin bloqueos" (comillas por claridad).

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

Adicionado por:Hernan Payrumani
Fecha:2013-11-16
Tiempo límite:1s
Límite del código fuente:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Lenguajes:C CSHARP CPP C++ 4.3.2 CPP14 JAVA
Fuente:Abierto de Informatica 2013

ocultar comentarios
2014-01-03 07:11:37 Eddy Cael
Existe un error en el enunciado: '1 ≤ xi < yi ≤ yi' debe ser '1 ≤ xi < yi ≤ N'
2014-01-03 06:47:13 Eddy Cael
Jaja... Publicaron mi problema :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.