Programacion Competitiva Bolivia

Sabías que existen ciudades subterráneas debajo de Bolivia? Muy pocos lo saben, pero ahora se está liberando está información a ciertas personas, ya que se encuentran en apuros.

Después de pelear con el primer brote del Apocalipsis Zombie cerca de Cochabamba (creías que el terremoto de Aiquile era producto de la naturaleza?),

La ciudad subterránea acaba de sufrir una gran inundación (problemas en las estructuras cercanas a los afluentes del Amazonas y el lago Titicaca) y una gran parte de los caminos que conectan las ciudades han sido destruidos!!!

Afortunadamente, el país es gran amigo de otro país subterráneo, TCtopía, ya que ambos países luchan contra los zombies y el pasatiempo preferido de estos países es la programación. Es por eso que TCtopía se encuentra con muchas ganas de ayudar al país amigo. Dicha ayuda consiste en el envío de puentes rectilíneos y enormes, los cuales conectarán nuevamente las ciudades inundadas.

Por más que TCtopía quiera ayudarnos, es un país que quiere enseñar a otros habitantes, no importa la situación. Es por eso que TCtopía no enviará la ayuda, si es que no se piden los requerimientos óptimos.

Un requerimiento, consiste en una longitud L. TCtopía enviará una cantidad sin límite de puentes, con la caracteristica que ningún puente tendrá una longitud mayor a L y un puente solamente puede unir 2 ciudades.

Un requerimiento óptimo, es aquel número L lo más pequeño posible, pero que sin embargo, pueda conectar todas las ciudades subterráneas.

Todas las ciudades subterráneas están conectadas, si es que existe al menos un camino transitable directo o indirecto entre cualquier par de ciudades.

Lastimosamente, las ciudades subterráneas están llenas de programadores, por lo que no cuenta con la tecnología necesaria para unir estos puentes de manera segura, para lograr mayores longitudes.

El objetivo principal, es que TODAS las ciudades están conectadas entre si, ya sea directa o indirectamente.

Se está liberando está información confidencial con algunos programadores de la superficie, para que los habitantes de la superficie puedan ayudar en el cálculo del requerimiento mínimo.

Entrada

La entrada comienza con un número NC, el número de casos de prueba. A continuación, existen NC casos de prueba, cada cual consiste en:

Un número N (2 <= N <= 1000), el número de ciudades subterráneas. Cada ciudad está numerada del 1 al N. Seguidamente, se muestran N posiciones de cada ciudad. Cada posición consiste en 2 coordenadas decimales (x,y), ( − 10⁹ ≤ x,y ≤ 10⁹). Finalmente, un número M seguido de M conexiones, una en cada linea. Cada conexión es un puente bidireccional que no fue destruido por la inundación y consiste en dos índices i,j que simbolizan la conexión entre la ciudad i y la ciudad j.

Salida

Por cada caso de prueba, imprimir el respectivo número de caso y el valor del requerimiento óptimo redondeado a la parte entera. Es decir, si el requerimiento óptimo es 3.9, la respuesta sería 3.

+----------------------+--------------------+
| Ejemplos de entrada  | Ejemplos de salida |
+----------------------+--------------------+
| 2                    | Caso 1: 1          |
| 3                    | Caso 2: 1          |
| 0 1                  |                    |
| 0 2                  |                    |
| 0 3                  |                    |
| 0                    |                    |
| 2                    |                    |
| 0 0                  |                    |
| 0 1.9                |                    |
| 0                    |                    |
+----------------------+--------------------+