Problem
در شهر N تحت شرایط نامشخصی، قلمرو یکی از کارخانه ها به منطقه ناهنجار تبدیل شد. تمامی ورودی های این قلمرو مسدود شده بود و خود آن منطقه صنعتی نامیده می شد. ساختمان های
N در منطقه صنعتی وجود دارد که برخی از آنها با جاده به هم متصل هستند. هر جاده ای را می توان در هر دو جهت طی کرد.
به استاکر تازه کار این وظیفه داده شد تا به انباری در منطقه صنعتی برسد. او چندین نقشه از قلمرو منطقه صنعتی را در آرشیو الکترونیکی پیدا کرد. از آنجایی که نقشه ها توسط افراد مختلف تهیه شده است، هر یک از آنها فقط اطلاعاتی در مورد برخی از جاده های منطقه صنعتی دارند. یک جاده می تواند در چندین نقشه ظاهر شود.
در راه، استالکر می تواند یک کارت را از بایگانی به تلفن همراه دانلود کند. وقتی یک نقشه جدید دانلود می کنید، نقشه قبلی در حافظه گوشی ذخیره نمی شود. استاکر فقط می تواند در امتداد جاده های مشخص شده در نقشه بارگذاری شده فعلی حرکت کند. هر بار دانلود نقشه 1 روبل هزینه دارد. برای به حداقل رساندن هزینه ها، استالکر باید چنین مسیری را انتخاب کند تا نقشه ها را تا حد امکان کمتر دانلود کند. Stalker می تواند چندین بار یک نقشه را دانلود کند و شما باید برای هر بار دانلود هزینه کنید. در ابتدا هیچ کارتی در حافظه تلفن همراه وجود ندارد.
نوشتن برنامه ای الزامی است که حداقل هزینه های لازم برای استاکر را برای رسیدن از ورودی منطقه صنعتی به انبار محاسبه کند.
ورودی:
- خط اول ورودی شامل دو عدد طبیعی
N و
K است (
\(2 <= N <= 2000 \ )؛
\(1 <= K <= 2000\)) — تعداد ساختمان های ناحیه صنعتی و تعداد نقشه ها به ترتیب. ورودی شهرک صنعتی با شماره
1 در ساختمان و انبار — در شماره ساختمان
N.
- در سطرهای زیر اطلاعاتی در مورد کارت های موجود وجود دارد. خط اول توضیحات کارت
iام حاوی عدد
ri — تعداد جاده های مشخص شده در نقشه
i-امین؛
- سپس رشته های
ri حاوی دو عدد طبیعی
a و
b (
\(1 <= a\)،
\(b <= N\)؛
\(a ? b\))، به این معنی که جاده ای در نقشه
i-ام وجود دارد که ساختمان های
a و
b< را به هم متصل می کند. / کد>. تعداد کل جاده های علامت گذاری شده در همه نقشه ها از 300000 تجاوز نمی کند (\(r_1 + r_2 + … + r_K <= 300000\)).
خروجی: چاپ یک عدد — حداقل مقدار هزینه های استاکر. اگر دسترسی به انبار غیرممکن است، شماره –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 |