파일 경로 | cho.sh

문제

바이트아사르는 위험하게 사는 것을 좋아한다. 가위를 든 채로 뛰어다니고, 예제 입력으로 확인해 보지도 않고 대회 문제의 답안을 제출하며, 자기 파일의 경로 이름 길이가 운영체제가 허용하는 최대 길이와 정확히 같기를 바란다. 리눅스라면 그 길이는 4095자다.

남의 컴퓨터에서 작업하다 보면 이 조건을 만족하지 않는 파일이 있다. 그러면 바이트아사르는 심볼릭 링크를 하나 만들어 새 경로 이름을 얻으려고 한다. 파일 시스템의 파일마다, 길이를 미리 정해 둔 심볼릭 링크 하나를 어딘가에 만들어서 그 파일을 길이가 정확히 $k$ 인 경로 이름으로 가리킬 수 있는지 판정하여라.

이름이 file인 파일이 디렉터리 dir1, dir2, ..., dirj 안에 차례로 들어 있으면 이 파일의 절대 경로는 /dir1/dir2/.../dirj/file이다. 루트 디렉터리는 /로 가리키고, 루트 디렉터리에 바로 들어 있는 파일의 절대 경로는 /file 꼴이다.

심볼릭 링크는 디렉터리를 가리키는 이름 붙은 지름길이고, 파일 시스템의 어느 디렉터리에나 놓을 수 있다. 이 문제에서 파일을 가리키는 심볼릭 링크는 만들 수 없다. 심볼릭 링크를 쓰면 같은 파일을 가리키는 다른 경로를 얻는다. 예를 들어 /에 /를 가리키는 이름 hello의 링크를 만들면 /dir/file, /hello/dir/file, /hello/hello/dir/file이 모두 같은 파일을 가리키고 경로 이름의 길이만 달라진다. /dir에 /를 가리키는 이름 hi의 링크를 만들면 /dir/file, /dir/hi/dir/file, /dir/hi/dir/hi/dir/file을 얻는다. 링크는 계층 구조에서 위쪽, 아래쪽, 옆쪽 어디를 가리켜도 되고, 링크가 놓인 디렉터리 자신을 가리켜도 된다. 경로 이름에 ./, ../, //는 쓸 수 없다.

입력

첫 줄에 세 양의 정수 $n$ , $m$ , $k$ 가 주어진다. $n$ 은 루트가 아닌 디렉터리의 개수, $m$ 은 파일의 개수, $k$ 는 원하는 경로 이름의 길이다. 루트 디렉터리의 번호는 0이고, 나머지 디렉터리에는 1번부터 $n$ 번까지, 파일에는 1번부터 $m$ 번까지 번호가 붙는다.

둘째 줄에 만들려는 심볼릭 링크 이름의 길이 $s$ 가 주어진다. 이름 자체는 중요하지 않고, 파일 시스템의 다른 이름과 겹치지 않는다고 가정한다.

이어서 루트가 아닌 디렉터리를 설명하는 $n$ 개의 줄이 주어진다. 그중 $i$ 번째 줄에는 두 정수 $p_i$ 와 $l_i$ 가 주어진다. $i$ 번 디렉터리의 이름 길이가 $l_i$ 이고, 이 디렉터리가 바로 들어 있는 부모 디렉터리의 번호가 $p_i$ 라는 뜻이다.

마지막으로 파일을 설명하는 $m$ 개의 줄이 주어진다. 그중 $j$ 번째 줄에는 두 정수 $p_j$ 와 $l_j$ 가 주어진다. $j$ 번 파일의 이름 길이가 $l_j$ 이고, 이 파일이 들어 있는 디렉터리의 번호가 $p_j$ 라는 뜻이다.

출력

파일마다 한 줄씩, 모두 $m$ 개의 줄을 출력한다. $j$ 번째 줄에는 길이가 $s$ 인 심볼릭 링크 하나를 만들어서 $j$ 번 파일을 길이가 정확히 $k$ 인 경로 이름으로 가리킬 수 있으면 YES를, 그럴 수 없으면 NO를 출력한다.

제한

$1 \le n, m \le 3000$
$1 \le k, s \le 10^6$
$0 \le p_i < i$
$0 \le p_j \le n$
모든 파일과 디렉터리의 이름 길이는 1 이상이고, 절대 경로의 길이는 $k$ 이하다.

노트

첫 번째 예제의 파일 시스템은 다음과 같다. 심볼릭 링크의 이름을 LL, 디렉터리 이름을 a와 bbbbb, 파일 이름을 차례로 ccccccccccccc, dddddddddd, eeee, fffffff라고 하자. 루트에는 디렉터리 a와 파일 fffffff가 있고, a에는 디렉터리 bbbbb와 파일 eeee가 있으며, bbbbb에는 파일 ccccccccccccc와 dddddddddd가 있다.

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

1번 파일은 절대 경로 /a/bbbbb/ccccccccccccc의 길이가 이미 22라서 링크를 쓰지 않아도 된다. 2번 파일은 /a 안에 /a를 가리키는 링크 LL을 만들어 /a/LL/bbbbb/dddddddddd로 가리킨다. 3번 파일은 /a 안에 /를 가리키는 링크 LL을 만들어 /a/LL/a/LL/a/LL/a/eeee로 가리킨다. 4번 파일은 링크를 어디에 만들어도 길이를 22로 맞출 수 없다.