## DMOPC '21 Contest 9 P3 - Terrible Trains

View as PDF

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

Author:
Problem type

The Terrible Trains Committee (TTC) runs a railway network consisting of stations connected by rail routes, each of the routes taking hour to travel in either direction. The 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 hour to travel in either direction regardless of which stations it connects.

Upon learning this news, commuters have reported to the TTC headquarters with a request. The -th of them would like for it to be possible to get from station to station in at most hours (their morning route) and from station to station in at most 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.

#### Constraints

Each rail route connects two different stations.

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

#### Input Specification

The first line contains integers and .

The next lines each contain integers and , the two stations that the -th rail route connects.

The next line contains an integer .

The next lines each contain integers , , , , , and , 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
3
1 6 3 7 8 4
3 5 3 7 8 1
1 6 3 3 5 1

#### Sample Output

YES
YES
NO