Problem
En la ciudad de N, en circunstancias poco claras, el territorio de una de las fábricas se convirtió en una zona anómala. Todas las entradas al territorio fueron bloqueadas, y en sí mismo se denominó zona industrial. Hay edificios
N en la zona industrial, algunos de ellos están conectados por carreteras. Cualquier camino se puede recorrer en ambas direcciones.
El acosador novato recibió la tarea de llegar al almacén en la zona industrial. Encontró varios mapas del territorio de la zona industrial en el archivo electrónico. Dado que los mapas fueron compilados por diferentes personas, cada uno de ellos contiene información solo sobre algunos caminos de la zona industrial. La misma carretera puede aparecer en varios mapas.
En el camino, el acosador puede descargar una tarjeta del archivo al teléfono móvil. Cuando descarga un nuevo mapa, el anterior no se almacena en la memoria del teléfono. El acosador solo puede moverse por los caminos marcados en el mapa cargado actualmente. Cada descarga de mapa cuesta 1 rublo. Para minimizar los costos, el acosador debe elegir esa ruta para descargar mapas la menor cantidad de veces posible. Stalker puede descargar el mismo mapa varias veces y tendrás que pagar por cada descarga. Inicialmente, no hay ninguna tarjeta en la memoria del teléfono móvil.
Se requiere escribir un programa que calcule la cantidad mínima de gastos necesarios para que un acosador llegue desde la entrada de la zona industrial hasta el depósito.
Entrada:
- la primera línea de la entrada contiene dos números naturales
N y
K (
\(2 <= N <= 2000 \ );
\(1 <= K <= 2000\)) — el número de edificios de la zona industrial y el número de mapas, respectivamente. La entrada a la zona industrial se encuentra en el edificio con el número
1, y el almacén — en el edificio número
N.
- en las siguientes líneas hay información sobre las tarjetas disponibles. La primera línea de la descripción de la tarjeta
ith contiene el número
ri — número de caminos marcados en el mapa
i-th;
- luego vienen las cadenas
ri que contienen dos números naturales
a y
b (
\(1 <= a\),
\(b <= N\);
\(a ? b\)), lo que significa que hay una carretera en el mapa
i-ésimo que conecta los edificios
a y
b< / código>. El número total de carreteras marcadas en todos los mapas no supera las 300 000 (\(r_1 + r_2 + … + r_K <= 300 000\)).
Salida: imprimir un solo número — el monto mínimo de los gastos del acosador. Si es imposible llegar al almacén, imprima el número –1.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
12 4
4
16
24
79
10 12
3
14
7 11
36
3
25
4 11
8 9
5
3 10
10 7
7 2
12 3
5 12 |
3 |