## Wesley's Anger Contest 4 Problem 7 - Squirrel Cities

View as PDF

Points: 25 (partial)
Time limit: 3.0s
Java 5.0s
Python 5.0s
Memory limit: 256M

Author:
Problem types

The squirrel nation is preparing to establish an advanced highway system to connect their cities. They are scattered among different cities and would like to build a highway network such that there is a path between any two cities. There are different potential highway plans that they are considering. The highway plan connects cities and , with a bidirectional highway that has a durability of , and takes time to complete.

Each highway in the network must have a minimum durability, and a maximum amount of time to completion. Since the squirrels are indecisive, they will ask you questions. Each question is in the form of two integers, , and . They want you to determine whether it is possible to build a highway network such that there is a path between any two cities, with each highway in the network having a durability of at least , and each highway taking no longer than time to complete.

For this problem, Python users are recommended to use PyPy over CPython.

#### Constraints

For this problem, you will be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

for all
for all
for all

#### Input Specification

The first line of input contains integers, , , and , representing the number of cities in the squirrel nation, the number of potential highway plans, and the number of questions they will ask you.

The next lines describe the highway plans. The line contains integers, , , , , indicating that the plan connects cities and with a bidirectional highway that has a durability of , and takes time to complete.

The next lines describe the questions the squirrels will ask. The line contains integers, , , indicating that the question is asking whether it is possible to build a highway network such that there is a path between any two cities, with each highway in the network having a durability of at least , and each highway taking no longer that time to complete.

#### Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output lines. The line should contain the answer to the query. If there is a way to build a highway network such that there is a path between any two cities, with each highway in the network having a durability of at least , and each highway taking no longer than time to complete, then output YES. Otherwise, output NO.

#### Sample Input 1

3 3 2
1 2 10 5
2 3 5 3
3 1 8 9
4 7
6 8

#### Sample Output 1

YES
NO

#### Sample Explanation 1

For the first question, the first and second highway plans can be built to satisfy the requirements.

For the second question, there is no possible way to build a highway network that satisfies all requirements.