Problem
In der Stadt H hat sich unter ungeklärten Umständen das Gebiet einer der Fabriken in eine abnorme Zone verwandelt. Alle Zufahrten zum Territorium wurden blockiert, und es wurde als Industriegebiet bezeichnet. Im Industriegebiet befinden sich
N Gebäude, von denen einige durch Straßen verbunden sind. Jede Straße kann in beide Richtungen befahren werden.
Der angehende Stalker erhielt die Aufgabe, in ein Lager im Industriegebiet zu gelangen. Er fand in einem elektronischen Archiv mehrere Karten des Industriegebiets. Da die Karten von verschiedenen Personen zusammengestellt wurden, gibt es auf jedem von ihnen nur Informationen über einige Straßen im Industriegebiet. Die gleiche Straße kann auf mehreren Karten vorhanden sein.
Unterwegs kann der Stalker eine Karte aus dem Archiv auf das Mobiltelefon herunterladen. Wenn Sie eine neue Karte einlegen, wird die vorherige Karte nicht im Telefonspeicher gespeichert. Der Stalker kann sich nur auf den Straßen bewegen, die auf der aktuell geladenen Karte markiert sind. Jeder Kartenladen kostet 1 Rubel. Um die Kosten zu minimieren, muss der Stalker eine Route auswählen, um die Karten so wenig wie möglich zu laden. Der Stalker kann die gleiche Karte mehrmals herunterladen und muss für jeden Download bezahlen. Anfangs befindet sich keine Karte im Speicher des Mobiltelefons.
Es ist erforderlich, ein Programm zu schreiben, das die Mindestkosten berechnet, die ein Stalker benötigt, um vom Eingang zum Industriegebiet zum Lager zu gelangen.
Eingabe:
- die erste Zeile der Eingabe enthält zwei natürliche Zahlen
N und
K (
\(2 <= N <= 2000\);
\(1 <= K <= 2000\)) — die Anzahl der Industriegebäuden und die Anzahl der Karten. Der Eingang zum Industriegebiet befindet sich im Gebäude mit der Nummer
1 und das Lagerhaus befindet sich im Gebäude mit der Nummer
N.
- in den folgenden Zeilen finden Sie Informationen zu den verfügbaren Karten. Die erste Zeile der
i-Karte enthält die Zahl
ri — die Anzahl der Straßen, die auf der
i-Karte angegeben sind;
- dann kommen
ri Zeilen mit zwei natürlichen Zahlen
a und
b (
\(1 <= a\),
\(b <= N\);
\(a ? b\)) bedeutet, dass auf der
i-Karte eine Straße vorhanden ist, die die Gebäude
a und
b verbindet. Die Gesamtanzahl der Straßen, die auf allen Karten markiert sind, überschreitet nicht 300.000 (
\(r_1 + r_2 + ... + r_K <= 300.000\)).
Ausgabe: Geben Sie eine Zahl als Mindestbetrag für Stalkerausgaben aus. Falls Sie das Lager nicht erreichen können, geben Sie
–1 aus.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
12 4
4
1 6
2 4
7 9
10 12
3
1 4
7 11
3 6
3
2 5
4 11
8 9
5
3 10
10 7
7 2
12 3
5 12 |
3 |