# include <cstdarg>
# include <cstdlib>
# include <type_traits>
# include <climits>
# include <cassert>
# include <cctype>
# include <cstring>
# include <set>
# include <vector>
# include <algorithm>
# include <numeric>
# include <cstdio>

namespace khin {
  using namespace std;
  namespace main {
    inline namespace source {
      template <typename T> constexpr T& cmin(T& a, T const& b) { return a = min(a, b); }
      template <typename T> constexpr T& cmax(T& a, T const& b) { return a = max(a, b); }
      inline namespace io {
        class Scanner {
          FILE* const stream; char buffer[BUFSIZ];
          char *head = buffer, *tail = buffer;
          public:
          Scanner(FILE* const stream = stdin) : stream(stream) {}
          Scanner(char const* const filename) : Scanner(fopen(filename, "r")) {}
          ~Scanner() { fclose(stream); }
          private:
          void flush() {
            assert(head == tail), tail = head = buffer;
            tail += fread(buffer, sizeof(char), BUFSIZ, stream);
          }
          public:
          char getc() {
            if (head == tail) flush();
            return assert(head != tail), *head++;
          }
          template <typename Unsigned, enable_if_t<is_unsigned<Unsigned>::value, int> = 0>
            Unsigned get() {
              char ch;
              while (!isgraph(ch = getc()) && ch != EOF);
              assert(isdigit(ch));
              Unsigned res(0);
              while (isdigit(ch)) res = res * 10 + (ch - '0'), ch = getc();
              return res;
            }
          template <typename T> T& read(T& value) { return value = get<T>(); }
          template <typename T, typename... U>
            void read(T& value, U&... args) { read(value), read(args...); }
        };
        class Printer {
          FILE* const stream; char buffer[BUFSIZ], *ptr = buffer;
          public:
          Printer(FILE* const stream = stdout) : stream(stream) {}
          Printer(char const* const filename) : Printer(fopen(filename, "w")) {}
          ~Printer() { flush(), fclose(stream); }
          public:
          void flush() {
            uint const tmp(fwrite(buffer, sizeof(char), ptr - buffer, stream));
            assert(tmp == ptr - buffer), ptr = buffer;
          }
          public:
          void putc(char const ch) {
            if (ptr - buffer == BUFSIZ) flush();
            *ptr++ = ch;
          }
          void puts(char const* s) { while (*s) putc(*s++); putc('\n'); }
          void put(char const* s) { while (*s) putc(*s++); }
          template <typename Unsigned, enable_if_t<is_unsigned<Unsigned>::value, int> = 0>
            void put(Unsigned value) {
              static char stk[CHAR_BIT * sizeof(Unsigned)], *top(stk);
              while (*top++ = value % 10 + '0', value /= 10);
              while (putc(*--top), top != stk);
            }
          void writeln() { putc('\n'); }
          template <typename T>
            void writeln(T const value) { put(value), putc('\n'); }
          template <typename T, typename... U>
            void writeln(T const value, U const... args)
            { put(value), putc(' '), writeln(args...); }
          void println(char const* fmt...) {
            va_list args;
            va_start(args, fmt);
            while (*fmt)
              if (*fmt == '%')
                switch (*(++fmt)++) {
                  case 'h' :
                    switch (*fmt++) {
                      case 'u' :
                        put((ushort)va_arg(args, int));
                        break;
                    }
                    break;
                  case 's' :
                    put(va_arg(args, char const*));
                    break;
                  case 'u':
                    put(va_arg(args, uint));
                    break;
                }
              else
                putc(*fmt++);
            putc('\n');
            va_end(args);
          }
        };
      }
    }
    namespace a { void main(); }
  }
}

int main() { khin::main::a::main(); }

namespace khin::main::a {
  Scanner scanner; Printer printer;
  namespace test_case {
    constexpr uint J_max(100'000), C_max(200'000);
    class disjoint_set_union {
      uint mo[J_max + 1], sz[J_max + 1];
      public:
      void init(uint const j) {
        iota(mo + 1, mo + j + 1, 1u);
        fill(sz + 1, sz + j + 1, 1u);
      }
      uint find(uint const x)
      { return mo[x] == x ? x : mo[x] = find(mo[x]); }
      uint size(uint const x) { return sz[find(x)]; }
      void merge(uint x, uint y) {
        if ((x = find(x)) == (y = find(y))) return;
        if (sz[x] < sz[y]) swap(x, y);
        mo[y] = x, sz[x] += sz[y], sz[y] = 0;
      }
    };
    struct junction { set<uint> n; uint mo; };
    uint J, C, A, Q; junction j[J_max + 1];
    disjoint_set_union dsu; vector<uint> L;
    uint da[J_max + 1], dq[J_max + 1];
    void clear() {
      for (uint i(1); i <= J; ++i) j[i] = junction();
      L.clear();
    }
    void calc_dist(uint const s, uint* const dist) {
      memset(dist + 1, 0xff, sizeof(uint) * J);
      static uint queue[J_max];
      auto head(queue), tail(queue);
      dist[*tail++ = s] = 0;
      while (head != tail) {
        uint const x(*head++);
        for (uint const y : j[x].n) if (!~dist[y])
          dist[*tail++ = y] = dist[x] + 1;
      }
    }
    void main(ushort const x) {
      scanner.read(J, C, A, Q), dsu.init(J);
      for (uint i(0); i < C; ++i) {
        uint const u(scanner.get<uint>()), v(scanner.get<uint>());
        j[u].n.insert(v), j[v].n.insert(u), dsu.merge(u, v);
      }
      calc_dist(A, da), calc_dist(Q, dq);
      if (dsu.find(A) != dsu.find(Q)) {
        printer.println("Case #%hu: %s", x, "SAFE");
        return clear();
      }
      uint const sum = [] {
        uint res(0);
        for (uint i(1); i <= J; ++i)
          if (dsu.find(i) == dsu.find(A))
            res += j[i].n.size();
        return res;
      } ();
      assert(!(sum % 2)), assert(sum / 2 >= dsu.size(A) - 1);
      if (sum / 2 < dsu.size(A)) {
        uint ans(0);
        for (uint i(1); i <= J; ++i)
          if (da[i] < dq[i]) cmax(ans, 2 * dq[i]);
        printer.println("Case #%hu: %u", x, ans);
        return clear();
      }
      for (uint i(1); i <= J; ++i)
        if (dsu.find(i) == dsu.find(A))
          if (j[i].n.size() == 1)
            L.push_back(i);
      while (!L.empty()) {
        uint const l(L.back()); L.pop_back();
        assert(j[l].n.size() == 1), j[l].mo = *j[l].n.begin();
        assert(j[j[l].mo].n.find(l) != j[j[l].mo].n.end());
        j[j[l].mo].n.erase(l), assert(j[j[l].mo].n.size());
        if (j[j[l].mo].n.size() == 1) L.push_back(j[l].mo);
      }
      uint const rt = [] {
        uint x(A);
        while (j[x].mo) x = j[x].mo;
        return x;
      } ();
      if (da[rt] < dq[rt]) {
        printer.println("Case #%hu: %s", x, "SAFE");
        return clear();
      }
      uint ans(0);
      for (uint i(1); i <= J; ++i)
        if (da[i] < dq[i]) cmax(ans, 2 * dq[i]);
      printer.println("Case #%hu: %u", x, ans);
      return clear();
    }
  }
  void main() {
    ushort const T(scanner.get<ushort>());
    for (ushort i(1); i <= T; ++i) test_case::main(i);
  }
}