안전한 장비 운반로

문제

한 천문대는 N개의 관측소로 이루어져 있고, 관측소 사이에는 양방향 통로가 M개 있다. 관측소는 1번부터 N번까지 번호가 붙어 있으며, 통로를 따라가면 어느 관측소에서든 다른 모든 관측소로 갈 수 있다. 같은 두 관측소를 잇는 통로는 둘 이상 없고, 자기 자신을 잇는 통로도 없다. 이 중 K개의 관측소는 진동 차단 설비를 갖춘 본관이다. 관측소 v에 대해 d(v)를 v에서 가장 가까운 본관까지 지나야 하는 통로 수의 최솟값이라 하자. 본관 자신의 d 값은 0이다. 정밀 장비를 S번 관측소에서 T번 관측소로 옮기려 한다. 운반 경로는 S에서 시작해 T에서 끝나는, 통로로 이어진 관측소의 나열이다. 장비는 본관에서 멀수록 진동의 영향을 크게 받으므로, 경로의 위험도를 경로에 포함된 모든 관측소(S와 T 포함)의 d 값 중 최솟값으로 정의한다. 이 값이 클수록 장비가 오래 보호받는다고 하여 이를 경로의 보호 지수라 부른다. 가능한 모든 경로 중 보호 지수가 최대가 되는 값 X를 구하고, 보호 지수가 X인 경로들 중 지나는 통로 수가 가장 적은 경로의 통로 수 L을 구하라. S와 T가 같으면 경로는 그 관측소 하나뿐이며 통로 수는 0이다.

입력

첫째 줄에 N, M, K, S, T가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, N-1 ≤ M ≤ 300,000, 1 ≤ K ≤ N, 1 ≤ S, T ≤ N) 둘째 줄에 본관인 서로 다른 K개의 관측소 번호가 주어진다. 이어지는 M개의 줄에 각각 통로가 잇는 두 관측소 번호 u, v가 주어진다. 모든 값은 정수이고, 그래프는 연결되어 있으며 중복 통로와 자기 자신을 잇는 통로는 없다.

출력

X와 L을 공백으로 구분하여 한 줄에 출력한다.

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

1 4

3 2 1 3 3
1
1 2
2 3

2 0

출처: Devin.KR 자체 제작