I Hate Ready to Program P5 - Hanging On By A (Multi) Thread

View as PDF

Submit solution

Points: 7
Time limit: 1.5s
Text 4.298s
Memory limit: 256M

Problem type

You're rushing to complete MyCreation when RtP starts throwing you a million errors! There seems to be syntax errors in one of the other java files in your (poorly) multi-threaded program. It would have been REALLY helpful if Ready to Program showed you syntax errors BEFORE you clicked "Run". However, there's no time to be angry at Ready to Program (well not now, but definitely later). You don't have much time left before the assignment deadline. You stare at your folder and notice you have N java files. It seems that you didn't put into much thought into naming your java files, so they're all just named 1.java, 2.java, 3.java, and so on until N.java. You know that there are M connections between two java files. If one of the two files has an error, the other file will throw you an error pointing towards the other file (in graph theory terms, all M edges are bi-directional.) You also know that 1.java is the main class, and it is the only file you have open on RtP right now. Your partner said that he might have a general idea of which files might be the issue, and created a list of Q files you need to open to check. For each of these files, what is the minimum number of files you need to open to reach it? Or is the file even connected to the main class?


1 \leq N,M \leq 10^5

1 < f_i \leq N

1 \leq b_i,e_i \leq N

1 \leq Q < N

Input Specifications

The first line will contain two space-separated integers, N,M.

The next M lines will contain two space-separated integers, b_i,e_i, showing a connection between those two files.

The next line will contain the integer Q.

The next Q lines will contain an integer, f_i, each on its own line.

Output Specifications

For each value of f_i, output an integer, d, on its own line, the minimum number of files you need to open not including the main file to reach file f_i, or -1 if the file is disconnected from the main class.

Sample Input

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

Sample Output


Sample Case Explanation

The shortest path from 1 to 4 is 1 -> 2 -> 4. The shortest path from 1 to 6 is 1 -> 2 -> 4 -> 6. 5 is not connected to any nodes, so we output -1. Note that there are possibly more than one unique shortest path. For example, 1 -> 3 -> 4 is also a possible shortest path to 4.


There are no comments at the moment.