DMOPC '21 Contest 9 P3 - Terrible Trains

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

The Terrible Trains Committee (TTC) runs a railway network consisting of N stations connected by M rail routes, each of the routes taking 1 hour to travel in either direction. The N stations are connected so that there is a sequence of routes between any two stations. Despite their terrible trains, the TTC has managed to obtain enough funding to add exactly one additional rail route to their network. This new route may be added between any two stations and will also take 1 hour to travel in either direction regardless of which stations it connects.

Upon learning this news, Q commuters have reported to the TTC headquarters with a request. The i-th of them would like for it to be possible to get from station S_i to station T_i in at most X_i hours (their morning route) and from station U_i to station V_i in at most Y_i hours (their evening route). As the railway designer, it is your job to tell each commuter whether it is theoretically possible for their request to be satisfied after adding the additional rail route.


2 \le N \le 3 \times 10^3

1 \le M \le 3 \times 10^3

1 \le a_i, b_i \le N

1 \le Q \le 10^6

1 \le S_i, T_i, X_i, U_i, V_i, Y_i \le N

Each rail route connects two different stations.

No two of the original rail routes connect the same pair of stations.

Subtask 1 [50%]

1 \le Q \le 3 \times 10^3

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line contains 2 integers N and M.

The next M lines each contain 2 integers a_i and b_i, the two stations that the i-th rail route connects.

The next line contains an integer Q.

The next Q lines each contain 6 integers S_i, T_i, X_i, U_i, V_i, and Y_i, as described in the problem statement.

Output Specification

For each commuter, output YES if it is possible to satisfy their request or NO otherwise.

Sample Input

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

Sample Output



There are no comments at the moment.