Benson is a very hungry boy and is in desperate need of \(k\) breakfasts. His house is also peculiar as doorways between rooms are one-way so on his quest to break his fast Benson wants to find out if he can move through his house of \(n\) rooms and \(e\) doorways from room \(u\) to room \(v\) moving through at most \(d\) doorways (he is also very lazy) for \(k\) \((u,v)\) pairs.

Given a description of one-way doorways between rooms in his house, \(k\) pairs of start/end rooms and \(d\), the maximum distance Benson is willing to move at a time help him find if he can reach room \(v\) from room \(u\) in at most \(d\) doorways.

Input Specification

The first line contains four space-separated integers \(n, e, k ,d\) \((1 \leq n \leq 10^4), (1 \leq e, d \leq n), (1 \leq k \leq 10^4)\). The next \(e\) lines contain two integers, \(u,v\), describing each doorway in Benson's house. The next \(k\) lines contain two integers, \(u,v\), a start/end pair of rooms.

Output Specification

\(k\) lines reading "YES" if Benson can reach \(v\) from \(u\) in at most \(d\) doorways and "NO" otherwise.

Sample Input 1

3 2 1 3
2 0
1 0
2 1

Sample Output 1

NO

Sample Input 2

3 2 1 3
2 1
0 2
0 1

Sample Output 2

YES

Sample Input 3

3 2 1 1
2 1
0 2
0 1

Sample Output 3

NO

Note

In the first case, there is no path at all from room 2 to room 1.

In the second case, there is a path of length = 2 from room 0 to room 1.

In the third case, there is no path less than 1 room away from room 0 to room 1.