이상한 나라의 추격전

Alice는 이상한 나라의 미궁에 갇혀 Queen of Hearts와 그 전령에게 쫓기고 있다! 미궁은 $1$부터 $\mathbf{J}$까지 번호가 매겨진 $\mathbf{J}$개의 교차점으로 이루어져 있으며, $\mathbf{C}$개의 양방향 통로로 연결되어 있다.

Alice와 Queen of Hearts은 번갈아 이동하며, 둘은 항상 상대방의 위치를 알고 있다. 어느 쪽이든 한 번의 이동에서는 현재 교차점에 머물거나, 통로로 연결된 다른 교차점으로 이동한다.

하지만 여왕의 전령은 여왕이 다음에 할 이동을 미리 알린다. 즉, 누구든 이동하기 전에 전령이 여왕의 첫 이동을 알린다. 그러고 나서 Alice가 먼저 이동한다. 이후 여왕은 이동할 때마다 이전의 예고를 따라야 하며, 그다음 전령이 알릴 수 있도록 자신의 다음 이동을 결정한다. Alice는 예고를 들으므로 자신의 이동을 하기 전에 항상 여왕의 다음 이동을 알고 있다.

둘 중 어느 한쪽이 이동한 뒤 Alice와 여왕이 같은 교차점에 있으면 Alice는 붙잡힌다. 그렇지 않으면 추격이 계속된다. 총 $10^9$번의 이동이 끝난 뒤에는, 그중 절반은 Alice의 이동이고 절반은 여왕의 이동이며, Alice와 여왕이 같은 교차점에 있지 않다면 여왕이 포기하여 Alice는 안전해진다.

Alice는 탈출하기 위해 최적으로 이동을 선택한다. 탈출할 수 없다면 붙잡힐 때까지의 총 이동 횟수를 최대화하도록 이동을 선택한다. 여왕은 가능한 한 적은 총 이동 횟수로 Alice를 붙잡기 위해 최적으로 이동을 선택한다.

미궁의 구조와 여왕 및 Alice의 초기 위치가 주어질 때, Alice가 여왕에게 붙잡히는지 알아내고, 붙잡힌다면 몇 번의 이동 만에 붙잡히는지 구한다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{A} \le \mathbf{J}$. $1 \le \mathbf{Q} \le \mathbf{J}$. $\mathbf{A} \ne \mathbf{Q}$. 모든 $i$에 대해 $1 \le \mathbf{U_i} \lt \mathbf{V_i} \le \mathbf{J}$. 모든 $i \ne j$에 대해 $(\mathbf{U_i}, \mathbf{V_i}) \ne (\mathbf{U_j}, \mathbf{V_j})$.

테스트 세트 1 (Visible Verdict)

시간 제한: 10초. $2 \le \mathbf{J} \le 30$. $1 \le \mathbf{C} \le 60$.

테스트 세트 2 (Hidden Verdict)

시간 제한: 60초. $2 \le \mathbf{J} \le 10^5$. $1 \le \mathbf{C} \le 2 \times 10^5$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 네 정수 $\mathbf{J}$, $\mathbf{C}$, $\mathbf{A}$, $\mathbf{Q}$이 포함된 한 줄로 시작하며, 각각 교차점의 수, 통로의 수, Alice가 시작하는 교차점, 여왕이 시작하는 교차점을 나타낸다. 이어서 $\mathbf{C}$개의 줄이 주어진다. 이 줄들 중 $i$번째 줄에는 두 정수 $\mathbf{U_i}$와 $\mathbf{V_i}$가 주어지며, 이는 $i$번째 통로가 교차점 $\mathbf{U_i}$와 $\mathbf{V_i}$을 양방향으로 연결한다는 뜻이다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, Alice가 총 $10^9$번의 이동 동안 붙잡히지 않을 수 있다면 $y$는 SAFE이다. 그렇지 않다면 $y$는 여왕이 Alice를 붙잡는 데 걸리는 총 이동 횟수이며, Alice와 여왕의 이동을 모두 포함한다.

예제 케이스 #1은 문제 설명에 그림으로 제시된 케이스이다. Alice의 최적의 첫 이동은 교차점 $4$로 이동하는 것이다.

예제 케이스 #2은 예제 케이스 #1과 같지만, 여왕이 교차점 $2$에서 시작한다. 여왕은 먼저 교차점 $4$로 이동하겠다고 예고하여 Alice를 붙잡을 수 있다. Alice가 교차점 $4$로 이동한다면 $2$번의 이동 만에 붙잡힌다. Alice는 제자리에 머물면서 여왕이 Alice가 있는 교차점 $5$로 이동할 때까지 기다리면 추가로 $2$번의 이동 동안 붙잡히지 않을 수 있다.

예제 케이스 #3에서는 여왕이 무엇을 하더라도 Alice에게 도달할 수 없다.

예제 케이스 #4에서 여왕은 Alice의 현재 교차점으로 이동하겠다고 예고하는 것으로 시작할 수 있다. Alice는 그 전에 이동해야 한다. Alice가 여왕이 이미 있는 곳으로 이동하면 즉시 붙잡히고, Alice가 제자리에 머물면 여왕이 이동할 때 붙잡힌다. 두 번째 선택지는 Alice와 여왕의 이동을 합쳐 $1$번이 아니라 총 $2$번의 이동이 필요하므로 더 낫다.