Problem
إحدى المنظمات عالية السرية ، التي لا يُسمح لنا بالكشف عن اسمها ، هي شبكة من المخابئ تحت الأرض
N المتصلة بأنفاق متساوية الطول ، والتي يمكن للمرء من خلالها الانتقال من أي مخبأ إلى أي آخر ( ليس بالضرورة بشكل مباشر). يتم التواصل مع العالم الخارجي من خلال مخارج سرية خاصة تقع في بعض المخابئ.
احتاجت المنظمة إلى وضع خطة إخلاء للموظفين في حالة الطوارئ. للقيام بذلك ، لكل من المخابئ ، تحتاج إلى معرفة المدة التي سيستغرقها الوصول إلى أقرب مخرج. بصفتك متخصصًا في مثل هذه المهام ، يتم توجيهك إلى حساب الوقت المطلوب لكل من المخابئ وفقًا لوصف معين لمباني المنظمة السرية للغاية. لراحتك ، تم ترقيم المخابئ من
1 إلى
N .
الإدخال: & nbsp؛
- يحتوي أول سطرين على رقمين طبيعيين
N ،
K (
\ (1 & lt؛ = N & lt؛ = 100000 \) ،
\ (1 & lt؛ = K & lt؛ = N \) ) & mdash؛ عدد المخابئ وعدد المخارج على التوالي ؛
- في السطر الثالث ،
K مفصولة بمسافات بأرقام مختلفة من
1 إلى
N ، تشير إلى أرقام المخابئ التي توجد بها المخارج ؛
- يحتوي السطر الرابع على الرقم
M (
\ (1 & lt؛ = M & lt؛ = 100000 \) ) & mdash؛ عدد الأنفاق ؛
- & nbsp؛ في ما يلي
M & nbsp؛ سطور تدخل أزواج من الأرقام - عدد المخابئ الموصولة بواسطة نفق.
يمكن لكل من الأنفاق التحرك في كلا الاتجاهين. لا يوجد لدى المؤسسة أنفاق تؤدي من مخبأ إلى نفسه ، ولكن يمكن أن يكون هناك أكثر من نفق بين زوج من المخابئ.
الإخراج: & nbsp؛ طباعة
N أرقام مفصولة بمسافات & mdash؛ الحد الأدنى من الوقت اللازم للوصول إلى المخرج لكل من المخابئ. افترض أن وقت السفر عبر نفق واحد هو
1 .
نبسب ؛
نبسب ؛
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
3
1
2 نبسب ؛
3
1 2
3 1
2 3
| 1 0 1 |
| 2 |
10
2
10 8 نبسب ؛
9
67
75
58
8 1
1 10
10 3
34
49
9 2 |
1 4 1 2 1 3 2 0 3 0 |