ACM metrosu

ACM şəhərində kifayət qədər spesifik bir yeraltı metro sistemi mövcuddur. Metronun hər bir xəttində hər iki istiqamətdə hərəkət etmək mümkündür. İki xətt kəsişə bilər ki, bu da sərnişinlərin kəsişmə nöqtəsində bir xəttin qatarından digər xəttin qatarına keçməsinə imkan verir. Sizin marşrutunuzun başlanğıc və sonu haradasa metro xətlərinin üzərindədir. Siz metro qatarlarında hərəkətə marşrutun başlanğıc stansiyasında başlayırsınız və marşrutun sonuna çatana qədər metro xətlərinin kəsişmə nöqtələrində qatarı dəyişə bilərsiniz. Sizdən tələb olunur ki, bu səyahəti pulsuz, başqa sözlə, bir bilet belə almadan başa vurasınız. Problem ondadır ki, bir neçə polis biletləri yoxlayır. Başqa sözlə, siz səyahətiniz zamanı bu polislərin heç biri ilə münaqişəyə girmək istəmirsiniz. İki vəziyyətdə polislərlə münaqişə yarana bilər: bir xəttdən digərinə qatarınızı dəyişən zaman xətlərin kəsişməsində, ya da sizin olduğunuz vaqonda biletlərin yoxlanması zamanı. Sizə polislərin ilkin mövqeləri məlumdur. Qeyd edək ki, əgər polislər xətlərin kəsişməsindədirsə, onlar yalnız siz bu kəsişmədə qatar dəyişirsinizsə, sizdən biletinizi təqdim etməyi xahiş edəcəklər. Yox, əgər polislər xəttdədirsə (amma xətlərin kəsişməsində deyildirlərsə), onlar yalnız sizinlə eyni vaqonda olduqda biletinizi göstərməyi xahiş edəcəklər. Xəritədə metroda olmayan polislər də var ki, siz onları nəzərə ala bilməzsiniz.

Məsələn, aşağıdakı şəkildə metronun beş xətti təsvir edilmişdir və üç polis qara dairə ilə qeyd edilmişdir. Siz l_1-- l_4 yolunda polislərlə qarşılaşmadan $s$-dən $d$-yə gedə bilərsiniz, lakin $s$-dən d'-ə polislərlə münaqişə olmadan çatmaq mümkün deyil.

Metro xətlərinin verilmiş yerləşməsinə, polislərin yerinə və sizin səyahətinizin başlanğıc və son nöqtəsinə görə tələb olunan marşrutu heç bir polislə qarşılaşmadan keçmək mümkün olub-olmadığını müəyyənləşdirməlisiniz.