Pathfinder 教授是万维网超链接结构方面的权威。为了建立他的假设,他一直在开发能够自动遍历超链接并分析 Web 结构的软件代理。今天,他产生了一个关于改进其软件代理的有趣想法。然而,他非常忙碌,需要优秀程序员的帮助。现在邀请你加入他的开发团队,为他的新型软件代理创建一个小巧但关键的软件模块。
在遍历超链接时,Pathfinder 的软件代理会增量生成已访问 Web 部分的地图。因此,代理需要维护已遍历超链接和已访问网页的列表。跟踪此类信息的一个问题是,两个或多个不同的 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 的实验揭示此类别名。
好吧……但这确实是一个真正的挑战,为了做到完美,你可能需要在程序中嵌入相当复杂的逻辑。我们担心即使像你们这样优秀的程序员也无法在五小时内完成它。因此,我们将问题简化了一些,并使其稍微有些不切实际。你应该专注于 URL 的路径部分(即上述示例中的 /ICPC/、/ICPC、/ICPC/../ICPC/、/ICPC/./ 和 /ICPC/index.html),并忽略方案部分(例如 http://)、服务器部分(例如 www.ehime-u.ac.jp)以及其他可选部分。你应该仔细阅读后续描述的规则,因为其中一些可能并非基于当今 Web 和 URL 的实际情况。
本问题中的每个路径部分都是一个绝对路径名,它指定了从根目录到分层(树状)目录结构中某个网页的路径。路径名总是以斜杠(/)开头,表示根目录,后跟由斜杠分隔的路径段。例如,/ICPC/index.html 是一个包含两个路径段 ICPC 和 index.html 的路径名。
除最后一个路径段外,所有路径段都应为目录名,最后一个应为存储网页的普通文件名。但是,我们有一个例外规则:路径名末尾的普通文件名 index.html 可以省略。例如,如果 index.html 是一个现有的普通文件名,则路径名 /ICPC/index.html 可以缩写为 /ICPC/。更准确地说,如果 ICPC 是根目录下现有目录的名称,且 index.html 是 /ICPC 目录下现有普通文件的名称,则 /ICPC/index.html 和 /ICPC/ 指向同一个网页。此外,最后一个路径段后的最后一个斜杠也可以省略。也就是说,例如,/ICPC/ 可以进一步缩写为 /ICPC。但是,/index.html 只能缩写为 /(单个斜杠)。
你应该特别注意由单个句点(.)或双句点(..)组成的路径段,它们始终被视为目录名。前者表示目录本身,后者表示其父目录。因此,如果 /ICPC/ 指向某个网页,则 /ICPC/./ 和 /ICPC/../ICPC/ 都指向同一个页面。同样,如果 ICPC2 是根目录下现有目录的名称,则 /ICPC2/../ICPC/ 也指向同一个页面;否则它不指向任何网页。注意,根目录没有任何父目录,因此诸如 /../ 和 /ICPC/../../index.html 之类的路径名无法指向任何网页。
你在这项工作中的任务是编写一个程序,检查给定的两个路径名是否指向现有的网页,如果是,则检查它们是否相同。
输入格式
输入包含多个数据集。每个数据集的第一行包含两个正整数 $N$ 和 $M$,两者均小于或等于 100,并由单个空格字符分隔。
数据集的其余部分包含 $N + 2M$ 行,每行包含一个长度最多为 100 个字符的语法正确的路径名。你可以假设每个由两个斜杠包围的路径段长度至少为 1。换句话说,任何路径名中都不会出现两个连续的斜杠。每个路径段不包含字母数字字符(即 ‘a’–‘z’、‘A’–‘Z’ 和 ‘0’–‘9’)和句点(‘.’)以外的任何内容。
前 $N$ 个路径名枚举了所有网页(普通文件)。每个现有的目录名在这些路径名中至少出现一次。你可以假设这些路径名不包含仅由单个或双个句点组成的路径段,并且最后一个路径段是普通文件名。因此,你不必担心 index.html 和单/双句点的特殊规则。你还可以假设这 $N$ 个路径名中没有两个指向同一个页面。
接下来的 $M$ 对路径名中的每一对都是一个问题:这两个路径名是否指向同一个网页?这些路径名可能包含单句点或双句点,并可能以斜杠结尾。它们可能包含不对应于现有目录或普通文件的名称。
一行中的两个零表示输入的结束。
输出格式
对于每个数据集,你的程序应输出 $M$ 个问题的答案,每个答案占一行。如果两个路径名都指向同一个网页,则每个答案应为 “yes”;如果至少有一个路径名没有指向输入中列出的前 $N$ 个网页中的任何一个,则为 “not found”;否则为 “no”。
样例
输入 1
5 6 /home/ACM/index.html /ICPC/index.html /ICPC/general.html /ICPC/japanese/index.html /ICPC/secret/confidential/2005/index.html /home/ACM/ /home/ICPC/../ACM/ /ICPC/secret/ /ICPC/secret/index.html /ICPC /ICPC/../ICPC/index.html /ICPC /ICPC/general.html /ICPC/japanese/.././ /ICPC/japanese/./../ /home/ACM/index.html /home/ACM/index.html/ 1 4 /index.html/index.html / /index.html/index.html /index.html /index.html/index.html /.. /index.html/../.. /index.html/ /index.html/index.html/.. 0 0
输出 1
not found not found yes no yes not found not found yes not found not found