You Can't Write Science Fiction Better Than This

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Yesterday, Henning fell asleep while his chem teacher elaborated on the world of quantum mechanics. Unfortunately, the world of quantum mechanics is closer than he thinks.

The next day, Henning walks into Massey to realize that the school has rearranged itself into a collection of N locations numbered 1,2,\ldots,N, each floating in its own alternate dimension. There are M two-way portals, each one taking exactly 1 second to traverse and connecting two distinct locations. No two portals connect the same pair of locations. Since Henning is also a UHC grandmaster, he spends exactly 0 seconds outside of traversing portals.

Henning's head might be a little frazzled by the destruction of physics, but he is not about to call in sick that day, since he has a math test. He needs to walk to his locker at location A then go to his math class at location B. The front entrance of the school, where Henning starts at, is at location 1. Due to the might of quantum mechanics, the locker, the classroom, and the entrance are not necessarily in distinct locations. The bell is about to ring, so what is the smallest amount of time it takes for Henning to get there?

Input Specification

On the first line, N (1 \le N \le 1\,000), M (1 \le M \le {N \choose 2}), A, B (1 \le A,B \le N), in that order, each separated by a single space. On the next M lines, there will be two distinct space separated integers V_1 and V_2 (1 \le V_1, V_2 \le N), signifying a portal that connects the locations V_1 and V_2.

Output Specification

The smallest amount of time in seconds it takes for Henning to walk from the front entrance to his math class while also passing through his locker. If there is no such path, output -1.

Sample Input 1

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

Sample Output 1


Explanation for Sample 1

Here is a visual representation, where each numbered circle represents a corresponding location and each line represents a portal. Henning can either walk the path 1 \to 2 \to 3 \to 4 or 1 \to 2 \to 5 \to 4 for a total of 3 portal jumps, or 3 seconds of time spent at the minimum.

Sample Input 2

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

Sample Output 2


Sample Input 3

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

Sample Output 3



There are no comments at the moment.