원더랜드 추격전

앨리스는 하트의 여왕과 그녀의 전령에게 쫓기며 원더랜드의 미로에 갇혀 있다! 미로는 $\mathbf{J}$개의 교차로와 $\mathbf{C}$개의 양방향 통로로 이루어져 있으며, 교차로에는 1번부터 $\mathbf{J}$번까지 번호가 붙어 있다.

앨리스와 여왕은 번갈아 가며 움직인다. 한 번의 이동은 현재 교차로에 머무르거나, 통로로 연결된 다른 교차로로 옮겨 가는 것이다.

전령은 여왕의 다음 이동을 미리 알린다. 아무도 움직이기 전에 전령이 여왕의 첫 이동을 발표한다. 그 다음 앨리스가 먼저 움직인다. 이후 여왕은 움직일 때마다 이전 발표를 따라야 하며, 그다음 이동을 정해 전령이 발표하게 한다. 앨리스는 발표를 듣기 때문에 자신이 움직이기 전에 여왕의 다음 이동을 항상 안다.

둘 중 누가 움직인 뒤에라도 앨리스와 여왕이 같은 교차로에 있으면 앨리스는 잡힌다. 그렇지 않으면 추격이 계속된다. 총 $10^9$번의 이동(앨리스와 여왕이 절반씩 한다) 후에도 둘이 다른 교차로에 있으면, 여왕은 포기하고 앨리스는 안전해진다.

앨리스는 탈출하도록 최적으로 움직인다. 탈출할 수 없다면, 잡힐 때까지의 총 이동 횟수가 최대가 되도록 움직인다. 여왕은 앨리스를 가능한 한 적은 총 이동 횟수로 잡으려고 최적으로 움직인다.

미로의 구조와 여왕, 앨리스의 시작 위치가 주어질 때, 앨리스가 여왕에게 잡히는지 판단하라. 잡힌다면 몇 번의 이동 후에 잡히는지 구하라.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 나온다. 각 테스트 케이스는 교차로 수 $\mathbf{J}$, 통로 수 $\mathbf{C}$, 앨리스의 시작 교차로 $\mathbf{A}$, 여왕의 시작 교차로 $\mathbf{Q}$, 이 네 정수가 적힌 줄로 시작한다. 이어서 $\mathbf{C}$개의 줄이 주어진다. $i$번째 줄에는 $i$번째 통로가 교차로 $\mathbf{U\_i}$와 $\mathbf{V\_i}$를 양방향으로 잇는다는 두 정수가 적혀 있다.

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

• $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은 문제 설명의 그림과 같은 경우이다. 앨리스의 최선의 첫 이동은 교차로 $4$로 가는 것이다.

예제 #2는 예제 #1과 같지만 여왕이 교차로 $2$에서 시작한다. 여왕은 먼저 교차로 $4$로 이동한다고 발표하여 앨리스를 잡을 수 있다. 앨리스가 교차로 $4$로 가면 $2$번의 이동 만에 잡힌다. 앨리스는 제자리에 머물면서 여왕이 자신이 있는 교차로 $5$로 올 때까지 기다리면, 두 번의 이동을 더 버틸 수 있다.

예제 #3에서는 여왕이 어떻게 움직여도 앨리스에게 닿을 수 없다.

예제 #4에서 여왕은 앨리스의 현재 교차로로 이동하겠다고 발표하며 시작할 수 있다. 앨리스는 그 전에 움직여야 한다. 앨리스가 여왕이 있는 교차로로 가면 바로 잡힌다. 앨리스가 제자리에 있으면 여왕이 움직일 때 잡힌다. 후자가 더 낫다. 앨리스와 여왕의 총 이동은 $1$번이 아니라 $2$번이 필요하기 때문이다.