Programacion Competitiva Bolivia

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-1 ≤ M ≤ N*(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 x_i y_i indica, por cada linea, que se debe proteger el camino entre la ciudad x_i y la ciudad y_i (1 ≤ x_i < yi ≤ y_i). Además, la lista debe estar ordenada en forma no decreciente primero por x_i y luego por y_i.

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