Mimi is attending a Thanksgiving feast! She lives in a town with 
~N~ buildings numbered from 
~1~ to ~N~ and 
~M~ unweighted bidirectional roads connecting them. The 
~i^\text{th}~ road connects buildings 
~a_i~ and 
~b_i~. Mimi is a good guest, so she wants to bring a gift for the host. However, Mimi is also a procrastinator! The Thanksgiving feast is soon and she hasn't bought a gift yet. There are 
~K~ buildings 
~s_1, s_2, \dots, s_K~ which sell gifts. Mimi is currently at building 
~A~ and the feast is at building 
~B~. She needs to visit at least one of the ~K~ buildings and go to the feast. Help her find the length of the shortest way to do so!
It is guaranteed that there exists a way. Mimi is allowed to pass through ~B~ before buying a gift.
Constraints
~1 \le A, B, a_i, b_i, s_j \le N~
~1 \le K \le N~
~1 \le M \le \binom N 2~
Subtask 1 [30%]
~1 \le K \le 1\,000~
~1 \le N \le 1\,000~
~1 \le M \le 2\,000~
Subtask 2 [30%]
~1 \le K \le 10~
~1 \le N \le 100\,000~
~1 \le M \le 200\,000~
Subtask 3 [40%]
~1 \le K \le 100\,000~
~1 \le N \le 100\,000~
~1 \le M \le 200\,000~
Input Specification
The first line of input will contain five space-separated integers ~N~, ~M~, ~K~, ~A~, ~B~.
The next line will contain ~K~ space-separated integers ~s_1, s_2, \dots, s_K~ representing the buildings which sell gifts.
The next ~M~ lines each contain two space-separated integers, ~a_i~ and ~b_i~.
Output Specification
Output a single integer, the shortest distance.
Sample Input 1
5 4 3 1 2
3 4 5
1 2
2 3
3 4
4 5
Sample Output 1
3
Explanation for Sample 1
Mimi starts at building 1. She passes by 
~B=2~, to head to 
~3~. She then returns to 
~2~, giving a total length of ~3~.
Sample Input 2
5 5 1 1 2
4
1 2
2 3
3 4
4 5
5 1
Sample Output 2
4
Comments
Does anyone mind taking a look at my code? I have WAs from each batch but I can't think of any case that would break my code. What I did was do BFS from the start and end points simultaneously until I reach the first store that both sides have already reached, in which case, I exit the program. Thanks in advance!
I dont think you should to the bfs simultaneously, rather you should do it separately.
Thank you for the feedback! But quick question, why is it faulty to do BFS from both sides simultaneously? I changed my code as you suggested and it passed.