Patoloji Yollar#3198
Professor Pathfinder, World Wide Web-də hiperlinklərin quruluşu üzrə tanınmış bir mütəxəssisdir. Öz nəzəriyyələrini əsaslandırmaq üçün o, hiperlinkləri avtomatik olaraq keçib Vebin strukturunu təhlil edən proqram agentləri hazırlayır. Bu gün o, proqram agentlərini təkmilləşdirmək üçün maraqlı bir ideya düşünüb. Lakin çox məşğuldur və yaxşı proqramçılardan kömək istəyir. Siz isə indi onun inkişaf komandasında iştirak etmək üçün dəvət olunmusunuz və onun yeni tip proqram agentlərinin kiçik, lakin vacib proqram modulunu hazırlamalısınız.
Hiperlinkləri keçdikcə, Pathfinder-in proqram agentləri ardıcıl olaraq ziyarət olunan Veb hissələrinin xəritəsini yaradırlar. Beləliklə, agentlər keçilmiş hiperlinklərin və ziyarət olunmuş veb səhifələrin siyahısını saxlamalıdırlar. Belə məlumatı izləməkdə bir problem də var ki, iki və ya daha çox fərqli URL eyni veb səhifəyə istinad edə bilər. Məsələn, aşağıdakı beş URL-dən birini yazmaqla, sevimli brauzerləriniz çox güman ki, sizi eyni veb səhifəyə – ACM ICPC Ehime müsabiqəsinin ana səhifəsinə aparacaq.
http://www.ehime-u.ac.jp/ICPC/ http://www.ehime-u.ac.jp/ICPC http://www.ehime-u.ac.jp/ICPC/../ICPC/ http://www.ehime-u.ac.jp/ICPC/./ http://www.ehime-u.ac.jp/ICPC/index.html
Sizin proqramınız Pathfinder-in eksperimentləri üçün belə alias-ları aşkar etməlidir.
Amma... bunu tam şəkildə və mükəmməl etmək üçün proqramınıza olduqca mürəkkəb məntiq yerləşdirməli olardınız. Qorxuruq ki, hətta əla proqramçılar belə bunu beş saata bitirə bilməz. Ona görə də, problemi bir az sadələşdiririk və bir qədər real olmayan hala gətiririk. Siz URL-lərin yalnız path hissələrinə (məsələn, yuxarıdakı nümunədə /ICPC/, /ICPC, /ICPC/../ICPC/, /ICPC/./ və /ICPC/index.html) diqqət yetirməlisiniz və sxem hissələrini (məs., http://), server hissələrini (məs., www.ehime-u.ac.jp) və digər optional hissələri nəzərə almamalısınız. Aşağıda təsvir olunan qaydaları diqqətlə oxumalısınız, çünki onların bəziləri bugünkü Veb və URL-lərin reallığına tam əsaslanmaya bilər.
Bu məsələdə hər bir yol hissəsi, kök qovluqdan (root directory) başlayaraq bəzi veb səhifəyə qədər marşrutu göstərən mütləq yol adıdır (absolute pathname), və bu marşrut ağacvari (tree-shaped) qovluq strukturunda qurulub. Pathname həmişə bir slash () ilə başlayır – bu kök qovluq üçün simvoldur – və sonra slash-larla ayrılmış yol seqmentləri gəlir. Məsələn, /ICPC/index.html iki yol seqmentindən ibarət bir pathname-dir: ICPC və index.html.
Bu seqmentlərin hamısı (sonuncu istisna olmaqla) qovluq adları olmalıdır, sonuncu isə veb səhifənin saxlandığı adi fayl adıdır. Amma bir istisna qaydamız var: pathnamelərin sonunda olan index.html adi fayl adı buradan çıxarıla bilər. Məsələn, /ICPC/index.html marşrutu /ICPC/ şəklində qısaldıla bilər, əgər index.html həqiqətən mövcud olan bir fayl adıdır. Dəqiq desək, əgər ICPC kök qovluğun altındakı mövcud bir qovluq, və index.html isə /ICPC qovluğunun altında mövcud olan adi fayl adı olsa, /ICPC/index.html və /ICPC/ eyni veb səhifəyə istinad edir. Həmçinin, son seqmentdən sonra olan sonuncu slash da çıxarıla bilər. Yəni, məsələn, /ICPC/ daha da qısaldılıb /ICPC şəklində yazıla bilər. Amma yalnız /index.html sadəcə / (bircə slash) şəklində qısaldıla bilər.
Tək nöqtədən () və ya ikiqat nöqtədən () ibarət olan yol seqmentlərinə xüsusi diqqət yetirməlisiniz: bunlar həmişə qovluq adları kimi qəbul olunur. Birincisi, həmin qovluğun özünü, ikincisi isə valideyn qovluğunu bildirir. Buna görə də, əgər /ICPC/ müəyyən bir veb səhifəyə istinad edirsə, həm /ICPC/./, həm də /ICPC/../ICPC/ eyni səhifəyə istinad edir. Həmçinin, /ICPC2/../ICPC/ də eyni səhifəyə istinad edər, əgər ICPC2 kök qovluğun altında mövcud bir qovluq adıdır; əks halda isə heç bir veb səhifəyə istinad etmir. Qeyd edək ki, kök qovluğun heç bir valideyn qovluğu yoxdur, buna görə də /../ və /ICPC/../../index.html kimi pathnamelər heç bir veb səhifəyə işarə edə bilməz.
Bu məsələdə sizin vəzifəniz iki verilmiş pathname-in mövcud veb səhifəyə istinad edib-etmədiyini yoxlamaq, və əgər belədirsə, onların eyni səhifəyə istinad edib-etmədiyini müəyyən etməkdir.
Girişdə bir neçə dataset var. Hər dataset-in ilk sətrində iki müsbət tam ədəd – və var, bunların hər biri -dən böyük deyil və aralarında bir boşluq var.
Sonrakı sətrlərdə N + 2M hər biri maksimum simvoldan ibarət sintaksis cəhətdən düzgün pathname verilib. Qəbul edə bilərsiniz ki, iki slash arasındakı hər bir path seqmentinin uzunluğu ən azı birdir. Başqa sözlə, heç bir pathnamede iki ardıcıl slash ola bilməz. Hər bir path seqmentində yalnız əlifba-rəqəm simvolları ('a'-'z', 'A'-'Z', '0'-'9') və nöqtələr ('.') ola bilər.
İlk pathname bütün veb səhifələrin (adi faylların) siyahısını verir. Mövcud olan hər bir qovluq adı bu pathnamelərdə ən azı bir dəfə iştirak edir. Qəbul edə bilərsiniz ki, bu pathnamelər yalnız adi fayl adları ilə bitir və heç biri yalnız tək və ya ikiqat nöqtədən ibarət seqmentlər daşımır. Buna görə də, index.html və tək/ikiqat nöqtə üçün xüsusi qaydalar barədə narahat olmağa ehtiyac yoxdur. Həmçinin, heç bir iki pathnamelər eyni səhifəyə istinad etmir.
Sonrakı pathnamelər cüt-cüt verilmiş suallardır: bu iki pathname eyni veb səhifəyə istinad edir? Bu pathnamelərdə tək və ya ikiqat nöqtələr ola bilər, sonları slash ilə bitə bilər. Onlarda mövcud olmayan qovluq və ya adi fayl adları ola bilər.
Bir sətrdə iki sıfır daxil testlərin sonunu göstərir.
Hər dataset üçün proqramınız suala cavab verməlidir, hər cavabı isə ayrıca sətrə çıxarmalıdır. Əgər hər ikisi eyni veb səhifəyə işarə edirsə, cavab **yes**; əgər ən azı biri girişdəki ilk veb səhifədən heç birinə uyğun gəlmirsə, cavab **not found**; başqa hallarda isə **no** olmalıdır.
Nümunə 1