Mock CCC '19 Contest 1 J5 - Best Friends

View as PDF

Submit solution

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

Author:
Problem type

jsumabat, AQT, Ninjaclasher, and liwi are very close friends. The BEST of friends.

Their respective locations are represented as an undirected graph with N nodes and M edges. Both jsumabat and Ninjaclasher are located at node A. jsumabat wants to travel to where liwi is, which is node S, and Ninjaclasher wants to travel to where AQT is, which is node T.

As jsumabat and Ninjaclasher are very close to each other, they would like to travel together for as long as possible. Therefore, jsumabat has made a job for you.

He wants you to find out two paths of minimum length starting in A, ending in S and T, respectively, such that they share the maximum number of edges.

Constraints

  • 1 \le N, M \le 10^5
  • 1 \le A, S, T \le N, A, S, T could potentially be equal to each other
  • A, S, and T are connected.

For 20% of the points, 1 \le N \le 100, and 1 \le M \le 200.

Input Specification

The first line of input will contain 2 space separated integers, N and M.

The second line of input will contain 3 space separated integers, A, S, and T.

The final M lines of input will contain a_i and b_i, representing that node a_i is connected to b_i, and vice versa.

Output Specification

You are to output a single integer, the maximum number of edges that jsumabat and Ninjaclasher will travel together on, while getting to each other's destination with the minimum distance.

Sample Input 1

8 10
1 5 3
1 4
1 7
1 8
4 6
7 5
8 2
2 5
2 3
6 2
5 3

Sample Output 1

2

Sample Explanation

They can follow the path 1 \rightarrow 7 \rightarrow 5, and then split, the remaining person heading to 3. Therefore, they will stay on 2 edges together.


Comments

There are no comments at the moment.