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 each floating in its own alternate dimension. There are two-way portals, each one taking exactly 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 then go to his math class at location . The front entrance of the school, where Henning starts at, is at location . 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?
On the first line, , , , , in that order, each separated by a single space. On the next lines, there will be two distinct space separated integers and , signifying a portal that connects the locations and .
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 or for a total of portal jumps, or 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