## Wesley's Anger Contest 5 Problem 4 - Prison Escape

View as PDF

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

Author:
Problem types

After rigging the squirrel nation's election and obtaining full control over the nation, Wesley has ordered the imprisonment of his enemy Besley.

In order to regain his authority and power, Besley needs to escape from prison. Little does Wesley know, Besley has an accomplice (you) that has access to the prison's surveillance system, who will help Besley safely escape the prison without running into any guards.

The prison has rooms labelled from to , with two-way passageways connecting pairs of rooms, with the passageway connecting room and . It is possible to travel between any pair of rooms using a series of passageways, and it can be shown that the shortest path between any two rooms is unique. Security is very tight, with guards patrolling a series of rooms connected with corridors. Running into any guard will result in severe punishment, which is why planning the escape will be a necessity.

Besley will ask you questions in the form of two pairs of integers and , which asks that whether or not, and the earliest time he will encounter a guard if he is travelling from room to room and the guard moves from room to room . Both Besley and the guard use the shortest path between the two rooms, and will only meet if they are both in the same room at the same time and neither of them have reached their destination room yet. They both leave their initial room at and take second to move to an adjacent room.

Time is running out for Besley, can you quickly answer all his questions?

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

#### Constraints

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

for all
for all
for all
for all
Only input where it is possible to travel between any pair of rooms using a series of passageways is allowed.

for all
for all

for all
for all
for all

for all
for all

for all
for all

#### Input Specification

The first line of input contains integers, and , representing the number of rooms in the prison, and the number of questions that Besley asks.

The next lines describe the passageways. Each line contains integers, and , indicating a two-way passageway between rooms and . Only input where it is possible to travel between any pair of rooms using a series of passageways is allowed.

The next lines describe the questions that Besley asks. Each line contains integers, , , , and , indicating that Besley is asking whether or not, and the earliest time he will encounter a guard if he is travelling from room to room and the guard moves from room to room .

#### 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 question. If Besley will encounter a guard if he is travelling from room to room and the guard moves from room to room , output a single integer equal to the earliest time that he will encounter the guard. Otherwise, output -1.

#### Sample Input 1

5 4
5 3
5 1
5 2
5 4
2 4 3 1
2 5 4 1
3 1 4 5
1 5 2 5

#### Sample Output 1

1
-1
-1
-1

#### Sample Explanation 1

For the first question, Besley will encounter the guard at in room .
For the second, third, and fourth questions, Besley will not encounter the guard before at least one of them reaches their destination.

#### Sample Input 2

4 3
1 2
2 3
3 4
1 3 2 4
2 3 3 2
1 4 3 1

#### Sample Output 2

-1
-1
1

#### Sample Input 3

6 2
5 4
4 3
2 3
3 6
1 2
1 6 4 6
1 6 5 6

#### Sample Output 3

-1
2

#### Sample Input 4

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

#### Sample Output 4

0
2

#### Sample Input 5

5 2
5 1
1 4
2 3
2 1
2 5 4 5
4 5 3 5

#### Sample Output 5

1
-1