You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

一个文件 $\tt file$ 都需要在一个包含很多文件 $\tt dir1,dir2,\cdots,dirj$ 的目录中，这个文件的 absolute file path 为 $\tt/dir1/dir2/\cdots/dirj/file$，根目录用 $\tt /$ 表示，每一个放在根目录下的文件的 absolute file path 的形式为 $\tt /file$。

符号链接指向一个已被命名的目录，可以看作一个快捷方式，他可以放置在任意目录下，注意，符号链接不能指向文件。比如，我们在 $\tt /$ 下放一个指向 $\tt /$ 的符号链接 $\tt hello$，那么，$\tt /dir/file$，$\tt /hello/dir/file$，$\tt /hello/hello/dir/dile$ 都指向同一个文件 $\tt file$。另比如，我们在 $\tt /dir$ 下放一个指向 $\tt /$ 的符号链接 $\tt hi$，那么，$\tt /dir/file$，$\tt /dir/hi/dir/file$，$\tt /dir/hi/dir/hi/dir/file$ 都指向同一个文件 $\tt file$。符号链接指向上一层，下一层，甚至同层都可以，但是不允许 $\tt ./$，$\tt ../$，$\tt //$ 之类的操作。

现在想问，是否能通过引入一个长为 $s$ 的符号链接使得找到一个文件的 absolute file path 长度恰好为 $k$？

输入格式

第一行三个整数 $n,m,k$ 代表除根目录之外的目录数，文件数和要求等于的路径长度。
第二行一个整数 $s$ 代表符号链接长。
接下来 $n$ 行每行两个整数 $p_i,l_i$ 描述一个目录，这个目录编号为 $l_i$，父目录编号为 $p_i$。
接下来 $m$ 行每行两个整数 $p_j,l_j$，描述一个文件，这个文件的长度为 $l_j$，父目录编号为 $p_j$。

输出格式

$m$ 行每行一个字符串代表是否能通过引入一个长为 $s$ 的符号链接使得找到编号为 $j$ 的文件的 absolute file path 长度恰好为 $k$，如果是的话输出 $\tt YES$，否则输出 $\tt NO$。

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

YES
YES
YES
NO

提示

样例 1 解释

假设符号链接名字为 $\tt LL$，目录名字为 $\tt a$，$\tt bbbbb$，文件名字为 $\tt ccccccccccccc$，$\tt dddddddddd$，$\tt eee$，$\tt fffffff$，根目录下包含目录 $\tt a$ 和文件 $\tt fffffff$，目录 $\tt a$ 下包含目录 $\tt bbbbb$ 和文件 $\tt eee$，目录 $\tt bbbbb$ 包含文件 $\tt ccccccccccccc$ 和 $\tt dddddddddd$。下面是形象化的表述：

/
|-- a
| |-- bbbbb
| | |-- ccccccccccccc
| | +-- dddddddddd
| +-- eeee
+-- fffffff

• 对于第 $1$ 个文件，满足条件的路径为 $\tt /a/bbbbb/ccccccccccccc$。
• 对于第 $2$ 个文件，满足条件的路径为 $\tt /a/LL/bbbbb/dddddddddd$。
• 对于第 $3$ 个文件，满足条件的路径为 $\tt /a/LL/a/LL/a/LL/a/eeee$。
• 对于第 $4$ 个文件，无满足条件的路径。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（33 pts）：$n,m \le 500$。
• Subtask 2（33 pts）：$n,m \le 3 \times 10^3$，符号链接最多被调用一次。
• Subtask 3（34 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le k,s \le 10^6$，$1\le m,n\le 3\times 10^3$。

说明

翻译自 BalticOI 2015 Day2 A File Paths。