Japón

E. Japón

Puntos 100 Validador token-caseless

Límite de tiempo 1s 250MB

Descripción

Japón planea la construcción de muchos caminos. Japón es una isla con N ciudades en su costa Este y Mciudades en su costa Oeste. K superautopistas serán construidas. Las ciudades en cada una de las costas están numeradas 1, 2, … de Norte a Sur. Cada superautopista es una línea recta y conecta una ciudad en la costa Este con una ciudad en la costa Oeste.

Una gran parte del presupuesto necesario es determinado por el número de cruces entre las superautopistas. A lo más, dos supercarreteras cruzan en el mismo lugar. Escribe un programa que calcule el número de cruces entre supercarreteras.

Entrada

El archivo de entrada empieza con T, el número de casos de prueba. Cada caso de prueba empieza con tres números: N, M y K. Cada una de las siguientes $K líneas contiene dos números: los números correspondientes a las ciudades conectadas por la superautopista. El primero es el número de la ciudad en la costa Este y el segundo es el número de la ciudad en la costa Oeste.

Salida

Para cada caso de prueba imprime una línea en la salida estándar:

Test case “número de caso de prueba”: “número de cruces”

Ejemplo

1

3 4 4

1 4

2 3

3 2

3 1 Test case 1: 5

Límites

• M, N <= 1000

________________________________________

Fuente: http://www.spoj.com/problems/MSE06H/

...