## GlobeX Cup '18 S4 - Reversed Dijkstra's

View as PDF

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 64M

Author:
Problem types

Note that this problem has no flavourtext.

You are given an unweighted bidirectional graph with nodes and edges. It is guaranteed the entire graph is connected. You are also given three integers, , and you would like to find a path from to with a distance that minimizes . However, in this path, you may not pass through any node more than once.

#### Input Specification

The first line will contain five space-separated integers, .

The next lines will each contain two space-separated integers, , indicating that node and node are connected by an edge. It is guaranteed there is only one edge between any nodes.

#### Output Specification

Output a path length that minimizes . If there are multiple values of , print the smallest one.

#### Sample Input 1

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

#### Sample Output 1

3

#### Sample Input 2

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

#### Sample Output 2

2