Патологические пути
Профессор Pathfinder — выдающийся специалист по структуре гиперссылок в Интернете. Для подтверждения своих гипотез он разрабатывает программные агенты, которые автоматически переходят по гиперссылкам и анализируют структуру сети. Сегодня у него появилась интересная идея по улучшению своих программных агентов. Однако он очень занят и нуждается в помощи опытных программистов. Вам предлагается присоединиться к его команде разработчиков и создать небольшой, но важный программный модуль для его нового типа программных агентов.
При переходе по гиперссылкам агенты Pathfinder постепенно создают карту посещенных частей сети. Таким образом, агенты должны поддерживать список пройденных гиперссылок и посещенных веб-страниц. Одна из проблем при отслеживании такой информации заключается в том, что два или более различных URL могут указывать на одну и ту же веб-страницу. Например, при вводе любого из следующих пяти URL ваш браузер, вероятно, приведет вас на ту же самую веб-страницу, которая, как вы, возможно, уже посещали, является домашней страницей конкурса ACM ICPC Ehime.
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.
Каждая часть пути в этой задаче является абсолютным путем, который указывает путь от корневого каталога до некоторой веб-страницы в иерархической (древовидной) структуре каталогов. Путь всегда начинается с косой черты (/), представляющей корневой каталог, за которой следуют сегменты пути, разделенные косой чертой. Например, /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+2M строк, каждая из которых содержит синтаксически правильный путь длиной не более 100 символов. Вы можете предположить, что каждый сегмент пути, заключенный между двумя косыми чертами, имеет длину не менее одного. Другими словами, две последовательные косые черты не могут встречаться в любом пути. Каждый сегмент пути не включает ничего, кроме буквенно-цифровых символов (т.е. 'a'-'z', 'A'-'Z', и '0'-'9') и точек ('.').
Первые N путей перечисляют все веб-страницы (обычные файлы). Каждое существующее имя каталога встречается хотя бы один раз в этих путях. Вы можете предположить, что эти пути не включают никаких сегментов пути, состоящих исключительно из одиночных или двойных точек, и что последние сегменты являются именами обычных файлов. Поэтому вам не нужно беспокоиться о специальных правилах для index.html и одиночных/двойных точек. Вы также можете предположить, что ни один из N путей не указывает на одну и ту же страницу.
Каждая из следующих M пар путей является вопросом: указывают ли два пути на одну и ту же веб-страницу? Эти пути могут включать одиночные или двойные точки и могут заканчиваться косой чертой. Они могут включать имена, которые не соответствуют существующим каталогам или обычным файлам.
Два нуля в строке указывают на конец ввода.
Выходные данные
Для каждого набора данных ваша программа должна выводить M ответов на M вопросов, каждый в отдельной строке. Каждый ответ должен быть "yes", если оба указывают на одну и ту же веб-страницу, "not found", если хотя бы один из путей не указывает ни на одну из первых N веб-страниц, перечисленных во входных данных, или "no" в противном случае.