/**
 * @file qoj4511F1.cpp
 * @author n685
 * @brief
 * @date 2023-07-16
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
std::ifstream cin;
std::ofstream cout;
using std::cerr;
#else
using std::cin;
using std::cout;
#define cerr                                                                   \
  if (false)                                                                   \
  std::cerr
#endif

void solve() {
  int n, m, a, q;
  cin >> n >> m >> a >> q;
  a--, q--;
  std::vector<std::vector<int>> adj(n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  std::vector<int> da(n, (int)1e9), dq(n, (int)1e9);
  auto bfs = [&](int s, std::vector<int> &d) {
    std::queue<int> qq;
    d[s] = 0;
    qq.push(s);
    while (!qq.empty()) {
      int node = qq.front();
      qq.pop();
      for (int i : adj[node]) {
        if (d[i] > d[node] + 1) {
          d[i] = d[node] + 1;
          qq.push(i);
        }
      }
    }
  };
  bfs(a, da);
  bfs(q, dq);

  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    for (int j : adj[i]) {
      // edge i, j
      if ((da[i] < dq[i]) ^ (da[j] < dq[j]))
        cnt++;
    }
  }
  cnt /= 2;
  if (cnt != 1) {
    cout << "SAFE\n";
    return;
  }

  // cnt = 1

  std::vector<bool> v(n);
  int md = 0;
  auto dfs = [&](auto &self, int node, int par) -> bool {
    v[node] = true;
    md = std::max(md, dq[node]);
    bool g = false;
    for (int i : adj[node]) {
      if (i == par || da[i] > dq[i])
        continue;
      if (v[i] || self(self, i, node))
        g = true;
    }
    return g;
  };
  if (dfs(dfs, a, -1)) {
    cout << "SAFE\n";
  } else
    cout << 2 * md << '\n';
}

int main() {
#ifdef LOCAL
  cin.open("input.txt");
  cout.rdbuf()->pubsetbuf(0, 0);
  cout.open("output.txt");
#else
  cin.tie(nullptr)->sync_with_stdio(false);
#endif

  int t;
  cin >> t;
  for (int tt = 1; tt <= t; ++tt) {
    cout << "Case #" << tt << ": ";
    solve();
  }
}