پاسخ - SGU 520

متن اصلی سوال : http://acm.sgu.ru/problem.php?contest=0&problem=520

ترجمه :

در یک کشور با n شهر آتش سوزی رخ داده ، به طوری که در ابتدا شهر پایتخت (با شماره ی 1) در روز یک آتش می گیرد و سپس در هر روز بعد همه ی همسایه های شهر های در حال سوختن نیز ، آتش می گیرند .
دو مامور آتش نشان یک روبات را برای خاموش کردن آتش به صورت نوبتی کنترل می کنند ( روز های فرد "Vladimir" و روز های زوج "Nikolay" ) ، این ربات در هر روز می تواند به یکی از شهر های مجاور برود ، و اگر روزی در یک شهرِ در حال سوختن باشد ، نابود می شود .
می دانیم که هیچ کدام از آتش نشان ها دوست ندارند در نوبت خودشان ربات نابود شود ، چون مجبور به پرداخت کردن جریمه به دولت می شود ، و همینطور می دانیم هر دوی آنها بسیار باهوش هستند .
می خواهیم بدانیم در نهایت چه کسی مجبور به پرداخت جرمیه می شود .

ورودی :

در اولین خط ورودی دو عدد n تعداد شهر ها و m  تعداد جاده های کشور داده می شود .




در هر کدام از خط های بعدی ورودی دو عدد a و b آمده که نشان می دهد بین این دو شهر جاده وجود داره .

هیچ کدام از شهر ها با بیشتر از یک جاده به هم وصل نیستند و بین هر دو شهر یک مسیر وجود دارد .

خروجی :

در تنها خط خروجی نام کسی که مجبور به پرداخت جریمه به دولت می شود را بنویسید .

ورودی نمونه :

4 3
1 2
1 3
2 4

خروجی نمونه :

Vladimir

 

---

راهنمایی :

1. سعی کنید گراف را به یک DAG (گراف جهت دار بدون دور) تبدیل کنید .
2. کد سوال را بزنید ! :-"

کد به زبان ++C