Negcycle. دورة سلبية
Problem
يتم إعطاء رسم بياني موجه مرجح. مطلوب لتحديد ما إذا كان يحتوي على دورة من الوزن السلبي. إنه مضمون أنه يمكن الوصول إلى جميع رؤوس الرسم البياني من النقطة الأولى.
الإدخال: & nbsp؛
يحتوي السطر الأول من ملف الإدخال على رقمين طبيعيين & nbsp؛ n & nbsp؛ & nbsp؛ and & nbsp؛ & nbsp؛ m & nbsp؛ & mdash؛ عدد رؤوس وحواف الرسم البياني على التوالي (& nbsp؛ n & le؛ 1 & nbsp؛ 111، m & nbsp؛ & le؛ 11 & nbsp؛ 111).
تحتوي سطور m التالية على وصف للحواف ، واحد لكل سطر. رقم الحافة الأول موصوف بثلاثة أرقام bi و ei و wi & mdash؛ عدد نهايات الضلع ووزنه ، على التوالي (1 & nbsp ؛ & le ؛ & nbsp ؛ bi ، & nbsp ؛ ei & nbsp ؛ & le ؛ & nbsp ؛ n ، & nbsp ؛ 100 & nbsp ؛ 000 & nbsp ؛ & le ؛ wi & nbsp ؛ & le ؛ & nbsp ؛ 100 & nbsp ؛ 000) . لاحظ أن الرسم يمكن أن يحتوي على حواف وحلقات متعددة.
الإخراج:
يجب أن يحتوي السطر الأول من ملف الإخراج على نعم إذا كان الرسم البياني يحتوي على دورة من الوزن السالب و لا & mdash؛ خلاف ذلك.
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
4 4
2 1-4
1 2 1
3 4 2
2 3 3
| نعم
|
| 2 |
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2
| لا
|