URI Online Judge | 1076

Diseño de Laberintos

Por Neilor Tonin, URI Brasil

Time Limit: 1

A Peter le encanta dibujar laberintos, y recientemente tuvo una idea: ¿cuál sería la cantidad mínima de movimientos necesarios de la pluma para dibujar un laberinto, siempre comenzando y terminando en la misma posición? Para hacer el juego más interesante, Peter decidió que no se le permite levantar la pluma del papel. Las plantillas para la construcción del laberinto son siempre cuadradas, 3 x 3, 4 x 4, 5 x 5 hasta un máximo de 7 x 7.

Para cada ejemplo, Peter debe especificar dónde se debe comenzar el dibujo y su tarea es determinar la cantidad de movimientos necesarios para dibujar el laberinto de Peter. Peter te recuerda que no tienes que preocuparte por los ciclos, porque no habrá ciclos en ninguno de los casos de prueba. Sin embargo, un caso de prueba puede tener una entrada 4 1 y otra entrada 1 4. Esto significa dos líneas que conectan estos mismos dos nodos. De todos modos no hará ninguna diferencia en el dibujo del laberinto porque la cantidad de movimiento debe ser igual.

Mira el siguiente ejemplo, en el laberinto A (4 x 4), Peter quiere comenzar en el nodo 0, dibujar todas las líneas y regresar al nodo 0. Para esto, el mínimo de movimientos posibles es 30. En el laberinto B (3 x 3), Pedro empieza en el nodo 1, dibuja todas las líneas y regresa al nodo 1. En este caso, necesita 10 movimientos para realizar este dibujo.


Entrada

La primera línea de entrada contiene un entero T (T < 100) que representa el número de casos de prueba. Cada caso de prueba comienza con una línea conteniendo un entero N ( N < X2, donde X es el tamaño del laberinto que puede ser desde 3 hasta 7). Este N es el nodo donde el dibujo debe comenzar y también finalizar. En la siguiente línea de entrada existen dos valores V y A que respectivamente presentan la cantidad de vertices y bordes del laberinto. Luego, siguen A líneas, cada una indicando el segmento de linea que Peter debe trazar el dibujo del laberinto deseado.

Salida

La salida debe contener un entero para cada caso de prueba. Este número es la cantidad de movimiento de la pluma que se debe hacer para dibujar el laberinto deseado, teniendo en cuenta que el inicio y el final son siempre desde el mismo punto (nodo) y que no se puede levantar el lápiz del papel.

Ejemplo de entrada Ejemplo de salida

2
0
16 15
0 4
2 3
6 2
8 9
10 9
8 12
14 15
14 10
6 5
10 11
11 7
4 8
0 1
1 2
12 13
1
9 6
1 2
1 4
4 7
7 8
4 1
4 3

30
10