Alice 被困在仙境的迷宫中，正被红心皇后和她的传令官追赶！迷宫由 $\mathbf{J}$ 个路口组成，编号为 $1$ 到 $\mathbf{J}$，并由 $\mathbf{C}$ 条双向走廊连接。

Alice 和红心皇后轮流移动，且双方始终知道对方的位置。一次移动（无论是谁）包括留在当前路口或移动到通过走廊与当前路口相连的另一个路口。

然而，皇后的传令官会提前宣布皇后下一次的移动。这意味着在任何人移动之前，他会先宣布皇后的第一次移动。然后，Alice 先移动。之后，皇后每次移动时，都必须遵守之前的宣布，并决定她的下一次移动，以便传令官进行宣布。Alice 可以听到这些宣布，因此她在做出自己的移动之前总是知道皇后的下一次移动。

如果 Alice 和皇后在其中任何一方移动后处于同一个路口，则 Alice 被抓住。否则，追逐继续。在总共 $10^9$ 次移动（Alice 和皇后各占一半）之后，如果 Alice 和皇后不在同一个路口，那么皇后将放弃，Alice 将安全。

Alice 会选择最优的移动策略来逃脱。如果她无法逃脱，她会选择最优的移动策略以最大化被抓住前的总移动次数。皇后会选择最优的移动策略，试图以尽可能少的总移动次数抓住 Alice。

给定迷宫的布局以及皇后和 Alice 的初始位置，判断 Alice 是否会被皇后抓住，如果会被抓住，计算需要多少次移动。

输入格式

输入的第一行包含测试用例的数量 $\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 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}$
• $1 \le \mathbf{U_i} < \mathbf{V_i} \le \mathbf{J}$，对于所有 $i$
• $(\mathbf{U_i}, \mathbf{V_i}) \ne (\mathbf{U_j}, \mathbf{V_j})$，对于所有 $i \ne j$

子任务 1 (8 分)

时间限制：10 秒。

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

子任务 2 (22 分)

时间限制：60 秒。

• $2 \le \mathbf{J} \le 10^5$
• $1 \le \mathbf{C} \le 2 \times 10^5$

样例

输入 1

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

输出 1

Case #1: SAFE
Case #2: 4
Case #3: SAFE
Case #4: 2

说明 1

样例 1 是题目描述中展示的情景。Alice 的最优第一步是移动到路口 $4$。

样例 2 与样例 1 相同，但皇后从路口 $2$ 开始。皇后可以通过先宣布移动到路口 $4$ 来抓住 Alice。如果 Alice 移动到路口 $4$，她将在 $2$ 次移动后被抓住。Alice 可以通过原地不动并等待皇后移动到她所在的路口 $5$，从而多坚持 $2$ 次移动。

在样例 3 中，无论皇后做什么，都无法到达 Alice 所在的位置。

在样例 4 中，皇后可以先宣布她将移动到 Alice 当前的路口。Alice 必须在此之前移动。如果 Alice 移动到皇后已经所在的路口，她会立即被抓住；如果 Alice 保持原地不动，那么当皇后移动时她会被抓住。第二个选择更好，因为它需要 $2$ 次总移动（Alice 和皇后各一次）而不是 $1$ 次。