Problem
في مدينة N ، في ظل ظروف غامضة ، تحولت أراضي أحد المصانع إلى منطقة شاذة. تم إغلاق جميع مداخل المنطقة ، وكانت تسمى نفسها المنطقة الصناعية. يوجد في المنطقة الصناعية أبنية
N بعضها متصل بالطرق. يمكن السير في أي طريق في كلا الاتجاهين.
تم تكليف المطارد المبتدئ بمهمة الوصول إلى المستودع في المنطقة الصناعية. وجد عدة خرائط لإقليم المنطقة الصناعية في الأرشيف الإلكتروني. نظرًا لأن الخرائط تم تجميعها من قبل أشخاص مختلفين ، فكل منها يحتوي على معلومات فقط حول بعض طرق المنطقة الصناعية. يمكن أن يظهر نفس الطريق على عدة خرائط.
في الطريق ، يمكن للمطارد تنزيل بطاقة واحدة من الأرشيف إلى الهاتف المحمول. عند تنزيل خريطة جديدة ، لا يتم تخزين الخريطة السابقة في ذاكرة الهاتف. يمكن للمطارد التحرك فقط على طول الطرق المحددة على الخريطة المحملة حاليًا. كل تنزيل خريطة يكلف 1 روبل. لتقليل التكاليف ، يحتاج المطارد إلى اختيار مثل هذا الطريق لتنزيل الخرائط بأكبر عدد ممكن من المرات. يمكن لـ Stalker تنزيل نفس الخريطة عدة مرات ، وسيتعين عليك الدفع مقابل كل تنزيل. في البداية ، لا توجد بطاقة في ذاكرة الهاتف المحمول.
مطلوب كتابة برنامج يقوم بحساب الحد الأدنى من النفقات اللازمة للمطارد للوصول من مدخل المنطقة الصناعية إلى المستودع.
الإدخال: & nbsp؛
- يحتوي السطر الأول من الإدخال على رقمين طبيعيين
N و
K (
\ (2 & lt؛ = N & lt؛ = 2000 \) ؛
\ (1 & lt؛ = K & lt؛ = 2000 \) ) & mdash؛ عدد مباني المنطقة الصناعية وعدد الخرائط على التوالي. يقع مدخل المنطقة الصناعية في المبنى مع الرقم
1 ، والمستودع & [مدش] ؛ في رقم المبنى
N .
- في الأسطر التالية توجد معلومات حول البطاقات المتاحة. يحتوي السطر الأول من وصف البطاقة
i على الرقم
r i & mdash؛ عدد الطرق المحددة على الخريطة رقم
i ؛
- & nbsp؛ ثم تأتي
r i سلاسل تحتوي على رقمين طبيعيين
a و
b (
\ (1 & lt؛ = a \) ،
\ (b & lt؛ = N \) ؛
\ (a؟ b \) ) ، مما يعني وجود طريق على الخريطة رقم
i -th التي تربط المباني
a و
b < / كود>. لا يتجاوز العدد الإجمالي للطرق التي تم وضع علامة عليها في جميع الخرائط 300000 ( \ (r_1 + r_2 +… + r_K & lt؛ = 300000 \) ).
الإخراج: & nbsp؛ طباعة رقم واحد & [مدش]؛ الحد الأدنى من نفقات المطارد. إذا كان من المستحيل الوصول إلى المستودع ، فقم بطباعة الرقم & ndash؛ 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 |