세종이의 특급 배송

Background

정보 나라에는 n개의 마을이 있다. 또한 신기하게도 마을은 트리 형태로 연결되어 있다. 즉 n-1개의 도로로 마을을 연결하고 있고, 사이클은 존재하지 않는다.

정보 나라에는 매년 m개의 행사가 진행되고, 행사는 두 마을을 연결하는 도로에서 진행된다. 행사가 진행되면 해당 도로를 막아 행사를 진행하므로, 두 마을 사이를 차를 이용하여 이동할 수 없다. 또한 같은날 여러개의 행사가 진행 될 수 있고, 한 도로에서 여러개의 행사가 동시에 진행될 수 도 있다.

예를 들어 A와 B마을을 연결하는 도로에서 행사가 진행되면 해당 도로는 사용하지 못한다.

정보 나라에서는 "신속 배송"이라는 배송 회사가 차를 이용하여 짐을 배송해주는 서비스를 진행하고 있다.

하지만 행사가 진행되는 도로를 사용하지 못해서 해당일에 배달을 못하는 경우가 종종 발생하고 있다.

예를 들어 아래와 같이 행사가 진행될 때,

E마을에서 F마을로 배송은 가능하지만 E마을에서 C마을로는 배송이 불가능하다.

"신속 배송"에서 배송 예약 일을 하고 있는 세종이는 예약 받은 배송 서비스를 못해 소비자에게 항의 전화를 자주 받고 있다.

세종이는 항의 전화를 받지 않기 위해 얘약을 받을 때, 정보 나라의 행사 일정을 참고하여 배송 가능 할 때만 예약을 받으려고 한다. 즉 배송을 못하는 경우에는 배송 예약을 받지 않으려고 한다.

세종이는 m개의 행사 일정을 가지고 있고 행사 일정을 바탕으로 마을A에서 마을B로의 배송서비스가 가능여부를 "YES"와 "NO"를 출력하는 프로그램을 작성하려고 한다.

세종이를 도와 프로그램을 작성하여 보자.

Input

첫 번째 줄에는 마을의 수 n, 행사의 수 m, 배달 예약 건수 k가 주어진다.

두 번째 줄부터 n번째 줄까지 도로가 연결하고 있는 마을 A, B가 공백을 기준으로 주어진다. (A마을과 B마을 연결)

n+1번째 줄부터 n+m번째 줄까지 행사 시작일 a, 종료일 b, 도로가 연결하고 있는 마을 A, B가 공백을 기준으로 주어진다.

n+m+1째 줄부터 n+m+k번째 줄까지 배달 예약과 관련된 날짜와 출발 도시 A, 도착 도시 B가 주어진다.

#1(10점)

(10<= n, m, k <=100), (1<= A, B, <=n), (1<=a, b, d<= 100)

#2(20점)

(10<= n, m, k <=100,000), (1<= A, B, <=n), (1<=a, d<= 100,000) (b = 100,001)

#3(30점)

(10<= n, m, k <=100,000), (1<= A, B, <=n), (1<=a, b, d<= 100,000), (a=b)

#4(40점)

(10<= n, m, k <=100,000), (1<= A, B, <=n), (1<=a, b, d<= 100,000)

Output

k개의 배달 예약에 대한 배달 가능 여부를 출력하시오.

(가능하면 "YES", 불가능하면 "NO"를 출력하시오.)

IO Example

입력 1

3 2 2

1 2

2 3

1 2 1 2

2 4 2 3

2 1 3

3 1 2

출력 1

NO

YES

입력 2

5 2 6

1 2

1 3

2 4

2 5

1 2 1 2

4 5 1 2

1 3 4

2 4 3

3 3 4

4 4 3

5 3 4

6 4 3

츨력 2

NO

NO

YES

NO

NO

YES

입출력2 설명

1일차(3에서 4로 배송 가능 : NO)	2일차(4에서 3으로 배송 가능 : NO)	3일차(3에서 4로 배송 가능 : YES)
4일차(4에서 3으로 배송 가능 : NO)	5일차(3에서 4로 배송 가능 : NO)	6일차(4에서 3으로 배송 가능 : YES)