Problem
Di bandar N, dalam keadaan yang tidak jelas, wilayah salah satu kilang bertukar menjadi zon anomali. Semua pintu masuk ke wilayah itu disekat, dan ia sendiri dipanggil zon perindustrian. Terdapat bangunan
N di zon perindustrian, sebahagian daripadanya disambungkan melalui jalan raya. Mana-mana jalan boleh dilalui dalam kedua-dua arah.
Penguntit baru diberi tugas untuk ke gudang di zon perindustrian. Dia menemui beberapa peta wilayah zon perindustrian dalam arkib elektronik. Memandangkan peta disusun oleh orang yang berbeza, setiap daripadanya hanya mengandungi maklumat tentang beberapa jalan di zon perindustrian. Jalan yang sama boleh muncul pada beberapa peta.
Dalam perjalanan, penguntit boleh memuat turun satu kad dari arkib ke telefon bimbit. Apabila anda memuat turun peta baharu, peta sebelumnya tidak disimpan dalam memori telefon. Penguntit hanya boleh bergerak di sepanjang jalan yang ditanda pada peta yang sedang dimuatkan. Setiap muat turun peta berharga 1 rubel. Untuk meminimumkan kos, penguntit perlu memilih laluan sedemikian untuk memuat turun peta sesedikit mungkin. Stalker boleh memuat turun peta yang sama beberapa kali, dan anda perlu membayar untuk setiap muat turun. Pada mulanya, tiada kad dalam memori telefon bimbit.
Ia dikehendaki menulis program yang mengira jumlah perbelanjaan minimum yang diperlukan untuk penguntit untuk pergi dari pintu masuk ke zon perindustrian ke gudang.
Input:
- baris pertama input mengandungi dua nombor asli
N dan
K (
\(2 <= N <= 2000 \ );
\(1 <= K <= 2000\)) — bilangan bangunan zon perindustrian dan bilangan peta, masing-masing. Pintu masuk ke zon perindustrian terletak di dalam bangunan dengan nombor
1 dan gudang — dalam nombor bangunan
N.
- dalam baris berikut terdapat maklumat tentang kad yang tersedia. Baris pertama perihalan kad
ith mengandungi nombor
ri — bilangan jalan yang ditanda pada peta
i-th;
- kemudian datang rentetan
ri yang mengandungi dua nombor asli
a dan
b (
\(1 <= a\),
\(b <= N\);
\(a ? b\)), bermakna terdapat jalan pada peta
i-th yang menghubungkan bangunan
a dan
b< / kod>. Jumlah bilangan jalan yang ditanda pada semua peta tidak melebihi 300,000 (\(r_1 + r_2 + … + r_K <= 300,000\)).
Output: cetak satu nombor — jumlah minimum perbelanjaan penguntit. Jika mustahil untuk sampai ke gudang, cetak nombor –1.
Contoh
| # |
Input |
Output |
| 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 |