题目描述

题目译自 BalticOI 2015 Day2 File Paths(FIL)，原题面见附加文件。
如欲转载翻译，请注明翻译者信息及转载出处。

Byteasar 喜欢冒险的生活。他带着剪刀跑，比赛交题不测样例，并且想要他的所有文件的路径名与操作系统所允许的最大值一样长（例如，在 Linux 下最长为 $4095$ 个字符）。

当 Byteasar 用其他人的电脑时，可能不是所有的文件都符合他的标准。在这种情况下，他尝试去引入符号链接（symlinks）并且用它们创建文件路径。你被要求去计算，对于文件系统的每一个文件，Byteasar 是否能引入仅一个符号链接（长度由他预先确定），使得这个文件的文件路径恰好有 $k$ 个字符。

如果一个文件名为 file 的文件包含在一系列名为 dir1，dir2，……，dirj 的目录之中，那么它的绝对文件路径（absolute file path）是 /dir1/dir2/.../dirj/file。根目录可以用 / 表示，并且每一个直接放在根目录下的文件的绝对路径形式为 /file。

符号链接是指向一个目录且已命名的快捷方式，它可以放置在文件系统的任意目录下。**在本题中，符号链接不允许指向文件！**使用符号链接，我们可以得到替代的文件路径。例如，我们在 / 下放一个指向 / 的符号链接 hello，那么，/dir/file，/hello/dir/file 与 /hello/hello/dir/file 指的都是同一个文件，但是文件路径长度不同。对于另一个例子，我们在 /dir 下放一个指向 /，名称为 hi 的符号链接，一些可以获得 file 的文件路径为：/dir/file，/dir/hi/dir/file，/dir/hi/dir/hi/dir/file。至于符号链接指向文件系统的上一层，下一层或者同层都是合法的，甚至返回它们放置的文件目录下也是可以的（即，在 /dir 下放置一个指向 /dir 的符号链接）。但是在目录名中，不允许 ./ 或 ../ 或 // 这样的文件操作。

输入格式

输入的第一行包含三个正整数 $n,m,k$，分别表示除了根目录外的目录数，文件个数和期望的文件目录名长度。根目录记为 $0$，其余的所有目录编号为 $1\sim n$。文件编号为 $1\sim m$。第二行包含符号链接名的长度 $s$（我们不关心名字本身，并且假设它不会与文件系统中的其余文件或文件夹冲突）。

接下来 $n$ 行描述出现在文件系统中的目录（除根目录之外），这些行中的第 $i$ 行描述编号为 $i$ 的目录，每行两个正整数 $p_i$ 和 $l_i$。它们表示标号为 $i$ 的目录的目录名为 $l_i$，并且它的父目录（即这个目录被直接包含的目录）为 $p_i$。保证 $p_i\lt i$。

最后 $m$ 行描述文件系统中的文件。这些行中的第 $j$ 行描述编号为 $j$ 的文件，并且包含两个整数 $p_j$ 和 $l_j$。它们表示编号为 $j$ 的文件的文件名长度为 $l_j$，并且父目录编号为 $p_j$。

所有文件和目录名的长度都为正数，并且它们的绝对路径长度最多为 $k$。

输出格式

你的程序应该输出 $m$ 行，每行包含一个单词 YES 或 NO，表示对这个问题的回答：通过引入长度为 $s$ 的符号链接，使得编号为 $j$ 的文件恰好有长度为 $k$ 的文件路径是否有可能？

样例

2 4 22
2
0 1
1 5
2 13
2 10
1 4
0 7

YES
YES
YES
NO

让我们把符号链接命名为 LL，文件夹命名为 a 和 bbbbb，并且文件名分别为 ccccccccccccc，dddddddddd，eee 和 fffffff。根目录包含一个文件夹 a 和文件 fffffff，文件夹 a 中包含文件夹 bbbbb 和文件 eeee，最后文件夹 bbbbb 包含两个文件 ccccccccccccc 和 dddddddddd。

对于第一个文件，绝对路径 /a/bbbbb/ccccccccccccc 的长度已经达到了目标长度，所以我们甚至不用符号链接就能达到要求。对于第二个文件，我们可以引入指向 /a 的符号链接 /a/LL，那么 /a/LL/bbbbb/dddddddddd 是符合要求的。对于第三个文件，我们需要引入指向 / 的符号链接 /a/LL，那么 /a/LL/a/LL/a/LL/a/eeee 是符合要求的。对于第四个文件我们无论加入指向哪里的符号链接都不能达到要求。

数据范围与提示

本题采用子任务式测评，只有一个子任务内所有测试点均正确才可获得此子任务的分数。

对于全部子任务，$1\le k,s\le 10^6$。

对于每个子任务满足的条件如下：