27824번 - Wonderland Chase 서브태스크다국어

문제

Alice is trapped in Wonderland's labyrinth, being chased by the Queen of Hearts and her herald! The labyrinth is a set of $\mathbf{J}$ junctions numbered 1ドル$ through $\mathbf{J},ドル connected by $\mathbf{C}$ bidirectional corridors.

Alice and the Queen of Hearts take turns making moves, and each knows the location of the other at all times. A move (by either of them) consists of either staying at the current junction or moving to another one that is connected to it by a corridor.

The Queen's herald, however, announces the next move the Queen makes in advance. That means that before anyone makes a move, he announces the Queen's first move. Then, Alice moves first. Then, each time the Queen moves, she must respect the previous announcement, and then decide her next move so the herald can announce it. Alice hears the announcements, so she always knows the Queen's next move before making her own.

If Alice and the Queen are at the same junction after either of them moves, then Alice is caught. Otherwise, the pursuit continues. After 10ドル^9$ total moves (half of them for Alice and half for the Queen), if Alice and the Queen are not in the same junction, then the Queen will give up and Alice will be safe.

Alice chooses her moves optimally to escape. If she cannot escape, she chooses her moves to maximize the total number of moves until she is caught. The Queen chooses her moves optimally to try to catch Alice in as few total moves as possible.

Given the labyrinth's layout and the initial locations of both the Queen and Alice, find out whether Alice will be caught by the Queen and, if so, in how many moves.

입력

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case starts with a line containing four integers $\mathbf{J},ドル $\mathbf{C},ドル $\mathbf{A},ドル and $\mathbf{Q}$: the number of junctions, the number of corridors, the junction where Alice starts, and the junction where the Queen starts, respectively. Then, $\mathbf{C}$ lines follow. The $i$⁠-⁠th of these lines contains two integers $\mathbf{U_i}$ and $\mathbf{V_i},ドル indicating that the $i$⁠-⁠th corridor bidirectionally connects junctions $\mathbf{U_i}$ and $\mathbf{V_i}$.

출력

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is SAFE if Alice can avoid being caught for 10ドル^9$ total moves. Otherwise, $y$ is the total number of moves (including Alice's and the Queen's) that it takes for the Queen to catch Alice.

제한

• 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}$.
• 1ドル \le \mathbf{U_i} \lt \mathbf{V_i} \le \mathbf{J},ドル for all $i$.
• $(\mathbf{U_i}, \mathbf{V_i}) \ne (\mathbf{U_j}, \mathbf{V_j}),ドル for all $i \ne j$.

Test Set 1 (8점)

시간 제한: 10 초

• 2ドル \le \mathbf{J} \le 30$.
• 1ドル \le \mathbf{C} \le 60$.

Test Set 2 (22점)

시간 제한: 60 초

2ドル \le \mathbf{J} \le 10^5$. 1ドル \le \mathbf{C} \le 2 \times 10^5$.

힌트

Sample Case #1 is the one pictured in the problem statement. Alice's optimal first move is to move to junction 4ドル$.

Sample Case #2 is the same as Sample Case #1 but the Queen starts at junction 2ドル$. The Queen can catch Alice by first announcing a move to junction 4ドル$. If Alice were to move to junction 4ドル$⁠, she would be caught in 2ドル$ moves. Alice can evade capture for an extra 2ドル$ moves by staying put and waiting until the Queen then moves to junction 5ドル$ where she is located.

In Sample Case #3, the Queen cannot reach Alice no matter what she does.

In Sample Case #4, the Queen can begin by announcing that she will move to Alice's current junction. Alice has to move before then. If Alice moves to where the Queen already is, she gets caught immediately; if Alice remains in place, then she gets caught when the Queen moves. The second option is better, since it requires 2ドル$ total moves (Alice's and the Queen's) instead of 1ドル$.