Description

A file $\tt file$ must be located in a directory that contains many directories $\tt dir1,dir2,\cdots,dirj$. The absolute file path of this file is $\tt/dir1/dir2/\cdots/dirj/file$. The root directory is denoted by $\tt /$. For a file placed directly under the root directory, its absolute file path has the form $\tt /file$.

A symbolic link points to a named directory and can be seen as a shortcut. It can be placed in any directory. Note that a symbolic link cannot point to a file. For example, if we place under $\tt /$ a symbolic link $\tt hello$ that points to $\tt /$, then $\tt /dir/file$, $\tt /hello/dir/file$, and $\tt /hello/hello/dir/dile$ all refer to the same file $\tt file$. As another example, if we place under $\tt /dir$ a symbolic link $\tt hi$ that points to $\tt /$, then $\tt /dir/file$, $\tt /dir/hi/dir/file$, and $\tt /dir/hi/dir/hi/dir/file$ all refer to the same file $\tt file$. A symbolic link may point to the parent directory, a child directory, or even a directory on the same level, but operations such as $\tt ./$, $\tt ../$, and $\tt //$ are not allowed.

Now the question is: is it possible, by introducing one symbolic link of length $s$, to make it possible to find an absolute file path of some file whose length is exactly $k$?

Input Format

The first line contains three integers $n,m,k$, representing the number of directories (excluding the root directory), the number of files, and the required path length $k$.
The second line contains an integer $s$, representing the length of the symbolic link.
The next $n$ lines each contain two integers $p_i,l_i$, describing a directory: this directory has ID $l_i$, and its parent directory has ID $p_i$.
The next $m$ lines each contain two integers $p_j,l_j$, describing a file: this file has length $l_j$, and its parent directory has ID $p_j$.

Output Format

Output $m$ lines. Each line is a string indicating whether, by introducing one symbolic link of length $s$, it is possible to find an absolute file path of length exactly $k$ for file $j$. If yes, output $\tt YES$; otherwise, output $\tt NO$.

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

YES
YES
YES
NO

Hint

Sample 1 Explanation

Assume the symbolic link name is $\tt LL$, the directory names are $\tt a$ and $\tt bbbbb$, and the file names are $\tt ccccccccccccc$, $\tt dddddddddd$, $\tt eee$, and $\tt fffffff$. The root directory contains directory $\tt a$ and file $\tt fffffff$. Directory $\tt a$ contains directory $\tt bbbbb$ and file $\tt eee$. Directory $\tt bbbbb$ contains files $\tt ccccccccccccc$ and $\tt dddddddddd$. A visual representation is:

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

• For file $1$, a path that satisfies the condition is $\tt /a/bbbbb/ccccccccccccc$.
• For file $2$, a path that satisfies the condition is $\tt /a/LL/bbbbb/dddddddddd$.
• For file $3$, a path that satisfies the condition is $\tt /a/LL/a/LL/a/LL/a/eeee$.
• For file $4$, no path satisfies the condition.

Constraints and Notes

This problem uses bundled tests.

• Subtask 1 (33 pts): $n,m \le 500$.
• Subtask 2 (33 pts): $n,m \le 3 \times 10^3$, and the symbolic link is used at most once.
• Subtask 3 (34 pts): no special restrictions.

For $100\%$ of the testdata, $1 \le k,s \le 10^6$, and $1 \le m,n \le 3\times 10^3$.

Notes

Translated from BalticOI 2015 Day2 A File Paths。

Translated by ChatGPT 5