Патологічні шляхи#3198

Патологічні шляхи

1 секунда

64 мегабайти

Середня

Професор Pathfinder є видатним фахівцем зі структури гіперпосилань у Всесвітній павутині. Для підтвердження своїх гіпотез він розробляє програмні агенти, що автоматично переходять за гіперпосиланнями і аналізують структуру Мережі. Сьогодні йому спала на думку цікава ідея щодо вдосконалення своїх програмних агентів. Але він дуже зайнятий і потребує допомоги талановитих програмістів. Вас запрошують приєднатися до його команди розробників і створити невеликий, але критично важливий програмний модуль для його нового типу програмних агентів.

Під час переходу за гіперпосиланнями агенти Pathfinder поступово створюють карту відвіданих частин Мережі. Тому агенти повинні зберігати список пройдених гіперпосилань і відвіданих веб-сторінок. Одна з проблем у веденні такої інформації — те, що два чи більше різних URL-адрес можуть вказувати на одну й ту ж веб-сторінку. Наприклад, ввівши будь-яку з наступних п'яти URL-адрес, ваш улюблений браузер, ймовірно, приведе вас на одну й ту ж веб-сторінку, яка, можливо, вам знайома — це домашня сторінка ACM ICPC Ehime Contest.

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

Ваша програма повинна знаходити такі псевдоніми для дослідів Pathfinder.

Але... насправді це було б дуже складне завдання, і для ідеального розв'язання вам, можливо, довелось би реалізувати надзвичайно складну логіку у своїй програмі. Ми боїмося, що навіть відмінні програмісти не змогли б упоратися з цим за п'ять годин. Тому ми дещо спростимо і водночас злегка відірвемо задачу від реальності. Ви повинні зосередитись лише на частинах шляху (тобто /ICPC/, /ICPC, /ICPC/../ICPC/, /ICPC/./ і /ICPC/index.html у наведеному вище прикладі) URL-адрес і ігнорувати частини схеми (наприклад, http://), частини з сервером (наприклад, www.ehime-u.ac.jp) та інші додаткові частини. Вам слід уважно прочитати правила, описані далі, оскільки деякі з них можуть не відповідати дійсності сучасного Інтернету та URL.

Кожна частина шляху (pathname) у цій задачі є абсолютним шляхом, що вказує маршрут від кореневої директорії до певної веб-сторінки у ієрархічній (структурі дерева) директорії. Шлях завжди починається зі слеша ( $/$ ), який означає кореневу директорію, далі йдуть сегменти шляху, розділені слешем. Наприклад, /ICPC/index.html — це шлях із двома сегментами: ICPC і index.html.

Усі ці сегменти, окрім останнього, повинні бути назвами директорій, а останній — назвою звичайного файлу, де зберігається веб-сторінка. Проте існує виняткове правило: звичайне ім'я файлу index.html наприкінці шляху можна опустити. Наприклад, шлях /ICPC/index.html можна скоротити до /ICPC/, якщо index.html є наявною назвою звичайного файлу. Точніше, якщо ICPC — назва наявної директорії безпосередньо під коренем, а index.html — звичайний файл безпосередньо під директорією /ICPC, то /ICPC/index.html і /ICPC/ вказують на одну й ту ж веб-сторінку. Крім того, останній слеш після останнього сегмента шляху також можна опустити. Тобто, наприклад, /ICPC/ можна ще скоротити до /ICPC. Проте /index.html можна скорочувати лише до / (один слеш).

Вам слід особливо уважно поставитись до сегментів шляху, що складаються з однієї крапки ( $.$ ) або двох крапок ( $..$ ), які завжди розглядаються як імена директорій. Перша позначає директорію саму, а друга — її батьківську директорію. Тому, якщо /ICPC/ вказує на певну веб-сторінку, то і /ICPC/./, і /ICPC/../ICPC/ вказують на ту ж сторінку. Також, /ICPC2/../ICPC/ вказує на ту ж сторінку, якщо ICPC2 — назва наявної директорії безпосередньо під коренем; інакше це не вказує на жодну веб-сторінку. Зверніть увагу, що коренева директорія не має батьківської директорії, отже такі шляхи, як /../ або /ICPC/../../index.html, не можуть вказувати на жодну веб-сторінку.

Ваше завдання у цій задачі — написати програму, яка перевіряє, чи вказують два задані шляхи на наявні веб-сторінки, і, якщо так, чи збігаються вони.

Вхідні дані

Вхід містить декілька наборів даних. Перша строка кожного набору містить два додатніх цілих числа $N$ і $M$ , обидва не більші за $100$ , розділені одним пробілом.

Далі у наборі йдуть $N + 2 M$ N + 2M рядків, у кожному з яких міститься синтаксично коректний шлях довжиною не більше $100$ символів. Можна вважати, що кожен сегмент шляху між двома слешами має довжину щонайменше один символ. Іншими словами, у жодному шляху не може бути двох послідовних слешів. Кожен сегмент шляху складається лише з англійських літер (від $^{'} a^{'}$ 'a' до $^{'} z^{'}$ 'z', $^{'} A^{'}$ 'A' до $^{'} Z^{'}$ 'Z'), цифр (від $^{'} 0^{'}$ '0' до $^{'} 9^{'}$ '9') або крапок ( $^{'} .^{'}$ '.').

Перші $N$ шляхів перераховують усі веб-сторінки (звичайні файли). Кожна наявна назва директорії зустрічається принаймні один раз у цих шляхах. Можна вважати, що ці шляхи не містять жодного сегмента, що складається лише з однієї чи двох крапок, а останні сегменти — це назви звичайних файлів. Отже, вам не потрібно турбуватись про спеціальні правила для index.html та одинарної/подвійної крапки. Також можна вважати, що жодні два з цих $N$ шляхів не вказують на одну й ту ж сторінку.

Далі йдуть $M$ пар шляхів — це запитання: чи вказують обидва шляхи на одну й ту ж веб-сторінку? Ці шляхи можуть містити одинарну чи подвійну крапку як сегмент та можуть закінчуватись слешем. Вони можуть містити імена, які не відповідають жодній із наявних директорій чи звичайних файлів.

Пара нулів у рядку вказує на кінець вхідних даних.

Вихідні дані

Для кожного набору даних ваша програма повинна вивести $M$ відповідей на $M$ питань, кожну в окремому рядку. Відповідь yes, якщо обидва шляхи вказують на одну й ту ж веб-сторінку, not found, якщо принаймні один із шляхів не вказує на жодну серед перших $N$ веб-сторінок у вхідних даних, або no в інших випадках.

Приклади

Приклад 1