Problem
N şehrinde, belirsiz koşullar altında fabrikalardan birinin bölgesi anormal bir bölgeye dönüştü. Bölgeye tüm girişler engellendi ve kendisine sanayi bölgesi adı verildi. Sanayi bölgesinde
N bina var, bazıları karayoluyla birbirine bağlı. Herhangi bir yol her iki yönde de kullanılabilir.
Acemi takipçiye, sanayi bölgesindeki depoya gitme görevi verildi. Elektronik arşivde sanayi bölgesi topraklarının birkaç haritasını buldu. Haritalar farklı kişiler tarafından derlendiğinden, her biri sadece sanayi bölgesinin bazı yolları hakkında bilgi içermektedir. Aynı yol birkaç haritada görünebilir.
Yolda takipçi, arşivden cep telefonuna bir kart indirebilir. Yeni bir harita indirdiğinizde, önceki harita telefonun hafızasında saklanmaz. Takipçi, yalnızca o anda yüklü olan haritada işaretlenmiş yollar boyunca hareket edebilir. Her harita indirme maliyeti 1 ruble. Maliyetleri en aza indirmek için, takipçinin haritaları olabildiğince az indirmek için böyle bir rota seçmesi gerekir. Stalker aynı haritayı birkaç kez indirebilir ve her indirme için ödeme yapmanız gerekir. Başlangıçta cep telefonunun hafızasında kart yoktur.
Bir stalker'ın sanayi bölgesi girişinden depoya ulaşması için gerekli minimum gider tutarını hesaplayan program yazılması gerekmektedir.
Giriş:
- girişin ilk satırı iki doğal sayı içerir
N ve
K (
\(2 <= N <= 2000) \ );
\(1 <= K <= 2000\)) — sırasıyla sanayi bölgesi bina sayısı ve harita sayısı. Sanayi bölgesinin girişi
1 numaralı binada, depo ise —
N numaralı binada.
- aşağıdaki satırlarda mevcut kartlar hakkında bilgi vardır.
iinci kartın açıklamasının ilk satırı
ri —
i'inci haritada işaretlenen yolların sayısı;
- sonra
a ve
b olmak üzere iki doğal sayı içeren
ri dizeleri gelir (
\(1 <= a\),
\(b <= N\);
\(a ? b\)), yani
i'inci haritada
a ve
b< binalarını birbirine bağlayan bir yol var / kod>. Tüm haritalarda işaretlenen toplam yol sayısı 300.000'i geçmez (\(r_1 + r_2 + … + r_K <= 300.000\)).
Çıktı: tek bir sayı yazdır — takipçinin minimum harcama tutarı. Depoya ulaşmak mümkün değilse –1 sayısını yazdırın.
Örnekler
| # |
Girdi |
Çıktı |
| 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 |