Problem
N市では、不明確な状況下で、工場の1つの領土が異常地帯に変わりました。領土へのすべての入り口が封鎖され、それ自体が工業地帯と呼ばれていました。工業地帯には
N 個の建物があり、そのうちのいくつかは道路でつながっています。どの道も両方向に通行できます。
初心者のストーカーは、工業地帯の倉庫に行く任務を与えられました。彼は、電子アーカイブで工業地帯の領土のいくつかの地図を見つけました。地図はさまざまな人によって編集されたため、それぞれの地図には工業地帯の一部の道路に関する情報しか含まれていません。同じ道路が複数の地図に表示されることがあります。
途中、ストーカーはアーカイブから 1 枚のカードを携帯電話にダウンロードできます。新しい地図をダウンロードすると、以前の地図は電話機のメモリに保存されません。ストーカーは、現在ロードされているマップにマークされている道路に沿ってのみ移動できます。各マップのダウンロードには 1 ルーブルの費用がかかります。コストを最小限に抑えるために、ストーカーはマップをダウンロードする回数をできるだけ少なくするために、そのようなルートを選択する必要があります。 Stalker は同じマップを複数回ダウンロードでき、ダウンロードごとに料金を支払う必要があります。最初は、携帯電話のメモリにカードがありません。
ストーカーが工業地帯の入り口から倉庫までの最低限必要な費用を計算するプログラムを書く必要があります。
入力:
- 入力の最初の行には、2 つの自然数
N と
K が含まれています (
\(2 <= N <= 2000 \ );
\(1 <= K <= 2000\)) —それぞれ、工業団地の建物の数と地図の数です。工業団地への入り口は、番号
1 の建物と倉庫 — にあります。建物番号
N にあります。
- 次の行には、利用可能なカードに関する情報があります。
i 番目のカードの説明の最初の行には、数字
ri が含まれています —
i 番目の地図にマークされた道路の数;
- 次に、2 つの自然数
a と
b を含む
ri 文字列 (
\(1 <= a\),
\(b <= N\);
\(a ? b\))、つまり
i 番目のマップに建物
a と
b< を結ぶ道路があることを意味します。 /コード>.すべてのマップにマークされた道路の総数は 300,000 を超えません (\(r_1 + r_2 + … + r_K <= 300,000\))。
出力: 単一の数値を出力します —ストーカーの最低限の出費。倉庫に行くことが不可能な場合は、番号 –1 を印刷してください。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 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 |