Problem
Nella città di N, in circostanze poco chiare, il territorio di una delle fabbriche si è trasformato in una zona anomala. Tutti gli ingressi al territorio furono bloccati, ed essa stessa fu chiamata zona industriale. Ci sono
N edifici nella zona industriale, alcuni dei quali sono collegati da strade. Qualsiasi strada può essere percorsa in entrambe le direzioni.
Al novizio stalker è stato affidato il compito di raggiungere il magazzino nella zona industriale. Ha trovato diverse mappe del territorio della zona industriale nell'archivio elettronico. Poiché le mappe sono state compilate da persone diverse, ognuna di esse contiene informazioni solo su alcune strade della zona industriale. La stessa strada può apparire su più mappe.
Lungo la strada, lo stalker può scaricare una carta dall'archivio sul cellulare. Quando scarichi una nuova mappa, quella precedente non viene salvata nella memoria del telefono. Lo stalker può muoversi solo lungo le strade segnate sulla mappa attualmente caricata. Ogni download della mappa costa 1 rublo. Per ridurre al minimo i costi, lo stalker deve scegliere tale percorso per scaricare le mappe il minor numero di volte possibile. Stalker può scaricare la stessa mappa più volte e dovrai pagare per ogni download. Inizialmente, non c'è nessuna scheda nella memoria del cellulare.
È necessario scrivere un programma che calcoli l'importo minimo di spesa necessario a uno stalker per arrivare dall'ingresso della zona industriale al magazzino.
Inserimento:
- la prima riga dell'input contiene due numeri naturali
N e
K (
\(2 <= N <= 2000 \ );
\(1 <= K <= 2000\)) — rispettivamente il numero di edifici della zona industriale e il numero di mappe. L'ingresso alla zona industriale si trova nell'edificio con il numero
1, e il magazzino — nell'edificio numero
N.
- nelle righe successive sono riportate le informazioni sulle carte disponibili. La prima riga della descrizione della
iesima carta contiene il numero
ri — numero di strade segnate sulla
i-esima mappa;
- poi vengono
ri stringhe contenenti due numeri naturali
a e
b (
\(1 <= a\),
\(b <= N\);
\(a ? b\)), che significa che c'è una strada sulla
i-esima mappa che collega gli edifici
a e
b< / codice>. Il numero totale di strade contrassegnate su tutte le mappe non supera 300.000 (\(r_1 + r_2 + … + r_K <= 300.000\)).
Output: stampa un singolo numero — l'importo minimo delle spese dello stalker. Se è impossibile raggiungere il magazzino, stampare il numero –1.
Esempi
| # |
Input |
Uscita |
| 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 |