Problem
Dans la ville de N, dans des circonstances peu claires, le territoire de l'une des usines s'est transformé en une zone anormale. Toutes les entrées du territoire étaient bloquées et elle-même s'appelait la zone industrielle. Il y a
N bâtiments dans la zone industrielle, certains d'entre eux sont reliés par des routes. N'importe quelle route peut être parcourue dans les deux sens.
Le harceleur novice a été chargé de se rendre à l'entrepôt de la zone industrielle. Il a trouvé plusieurs cartes du territoire de la zone industrielle dans les archives électroniques. Étant donné que les cartes ont été compilées par différentes personnes, chacune d'elles ne contient que des informations sur certaines routes de la zone industrielle. La même route peut apparaître sur plusieurs cartes.
En chemin, le harceleur peut télécharger une carte de l'archive sur le téléphone portable. Lorsque vous téléchargez une nouvelle carte, la précédente n'est pas enregistrée dans la mémoire du téléphone. Le harceleur ne peut se déplacer que le long des routes marquées sur la carte actuellement chargée. Chaque téléchargement de carte coûte 1 rouble. Pour minimiser les coûts, le harceleur doit choisir un tel itinéraire afin de télécharger les cartes le moins de fois possible. Stalker peut télécharger la même carte plusieurs fois, et vous devrez payer pour chaque téléchargement. Initialement, il n'y a pas de carte dans la mémoire du téléphone portable.
Il est nécessaire d'écrire un programme qui calcule le montant minimum des dépenses nécessaires pour qu'un harceleur se rende de l'entrée de la zone industrielle à l'entrepôt.
Entrée :
- la première ligne de l'entrée contient deux nombres naturels
N et
K (
\(2 <= N <= 2000 \ );
\(1 <= K <= 2000\)) — le nombre de bâtiments de la zone industrielle et le nombre de cartes, respectivement. L'entrée de la zone industrielle se trouve dans le bâtiment portant le numéro
1, et l'entrepôt — dans le bâtiment numéro
N.
- dans les lignes suivantes, il y a des informations sur les cartes disponibles. La première ligne de la description de la
ième carte contient le numéro
ri — nombre de routes marquées sur la
i-ième carte ;
- puis viennent les chaînes
ri contenant deux nombres naturels
a et
b (
\(1 <= a\),
\(b <= N\) ;
\(a ? b\)), ce qui signifie qu'il y a une route sur la
i-ième carte reliant les bâtiments
a et
b< /code>. Le nombre total de routes marquées sur toutes les cartes ne dépasse pas 300 000 (\(r_1 + r_2 + … + r_K <= 300 000\)).
Sortie : imprimer un seul numéro &mdash ; le montant minimum des dépenses du harceleur. S'il est impossible de se rendre à l'entrepôt, imprimez le numéro –1.
Exemples
| # |
Entrée |
Sortie |
| 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 |