Ölkədə yanğın#3682
İnanılmaz istilik və yağıntının olmaması səbəbindən kiçik "Yarz və Eva" adasında yerləşən ölkəni dəhşətli yanğınlar bürüyüb. Xilasetmə işçilərinin koordinasiyalı fəaliyyəti sayəsində ölkənin bütün sakinləri yaxın planetlərə təxliyə edilib.
Ölkəni xilas etmək üçün yalnız kiçik bir yanğınsöndürən robot qalıb. Robot, paytaxtdan başqa, bütün şəhərləri söndürməyi bacarıb. Lakin bütün maye tükəndiyindən ölkə yanmağa məhkumdur.
Alov çox sürətlə yayılır, buna görə də hər gün yanğın artıq yanan şəhərlərlə yol ilə birləşən bütün şəhərləri məhv edir. Robot artıq heç nəyi söndürə bilmir, onun edə biləcəyi yeganə şey - alovdan qaçmaqdır. Robotun sürəti alovun sürətinə bərabərdir, buna görə də bir gün ərzində robot qonşu şəhərə keçə bilər.
Robotu növbə ilə Nikolay və Vladimir adlı iki pilot idarə edir, onlar Yer kürəsinin təbii peykində yerləşirlər. Robot artıq xilas edilə bilməsə də və ondan heç bir fayda olmasa da, pilotlar onun öz növbələrində məhv edilməməsi ilə çox maraqlanırlar. Robotun itirilməsi üçün əmək haqqından əhəmiyyətli bir çıxarış nəzərdə tutulur.
Birinci gün robot paytaxtda (1 nömrəli şəhərdə) yerləşir. Birinci gün robotu Nikolay idarə edir və onu 1 ilə birləşən istənilən şəhərə yönləndirə bilər. Sonra pilotlar növbələşirlər. Beləliklə, hər gün robotun edə biləcəyi yeganə şey - onun cari mövqeyi ilə qonşu olan istənilən şəhərə keçməkdir.
Birinci gün yalnız paytaxt yanır. Hər növbəti gün artıq yanan şəhərlərlə yollarla birləşən bütün şəhərlər əlavə olaraq yanır.
Əgər pilot robotu yanan şəhərdə saxlayırsa və ya onu artıq yanan şəhərə yönləndirirsə, robot alova dözmür və məhv olur. Hər iki pilotun optimal davranışı ilə itirilmiş robot üçün kim cərimə ödəyəcək, müəyyən etməyə çalışın. Nəzərə alın ki, bir dəfə yanmağa başlayan şəhər uzun müddət yanmağa davam edir (məsələdə nəzərdən keçirilən vaxtdan daha çox).
Birinci sətirdə ölkədəki şəhərlərin n və yolların m sayı verilir (2 ≤ n, m ≤ 1000).
Növbəti m sətirdə yollar təsvir edilir: a, b - yollarla birləşən şəhərlərin nömrələri (1 ≤ a ≤ n, 1 ≤ b ≤ n,a ≠ b). Yollar ikitərəflidir, hər hansı bir şəhər cütü arasında bir yoldan çox yoxdur. Hər hansı iki şəhər arasında bir yol mövcuddur.
Çıxış faylına hər iki pilotun optimal davranışı ilə itirilmiş robot üçün cərimə ödəyəcək pilotun adını yazın ("Nikolay" - əgər bu Nikolaydır, "Vladimir" - əgər bu Vladimirdir).
Nümunə 1