# if not KHIN_SOURCE_H

# define KHIN_SOURCE_H true

# include <cstdarg>
# include <cstdlib>
# include <type_traits>
# include <utility>
# include <climits>
# include <cassert>
# include <cctype>
# include <cstring>
# include <map>
# include <set>
# include <vector>
# include <iterator>
# include <algorithm>
# 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); }
      template <typename T, class Compare>
        constexpr T& cmin(T& a, T const& b, Compare const comp)
        { return a = min(a, b, comp); }
      template <typename T, class Compare>
        constexpr T& cmax(T& a, T const& b, Compare const comp)
        { return a = max(a, b, comp); }
      template <typename T>
        constexpr pair<T&, T&> cminmax(T& a, T& b)
        { return pair<T&, T&>(a, b) = minmax(T(a), T(b)); }
      template <typename T>
        constexpr pair<T, T>& cminmax(pair<T, T>& a)
        { return a = minmax(T(a.first), T(a.second)); }
      template <typename T, class Compare>
        constexpr pair<T&, T&> cminmax(T& a, T& b, Compare const comp)
        { return pair<T&, T&>(a, b) = minmax(T(a), T(b), comp); }
      template <typename T, class Compare>
        constexpr pair<T, T>& cminmax(pair<T, T>& a, Compare const comp)
        { return a = minmax(T(a.first), T(a.second), comp); }
      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() {
            tail = head = buffer;
            tail += fread(buffer, sizeof(char), BUFSIZ, stream);
          }
          public:
          char getc() {
            if (head == tail) flush();
            return head == tail ? EOF : *head++;
          }
          template <typename T, enable_if_t<is_signed_v<T>, int> = 0>
            T get() {
              char ch;
              while (!isgraph(ch = getc()) && ch != EOF);
              int const sign(ch == '-' ? ch = getc(), -1 : +1);
              assert(isdigit(ch));
              T res(0);
              while (isdigit(ch))
                res = res * 10 + sign * (ch - '0'), ch = getc();
              return res;
            }
          template <typename T, enable_if_t<is_unsigned_v<T>, int> = 0>
            T get() {
              char ch;
              while (!isgraph(ch = getc()) && ch != EOF);
              assert(isdigit(ch));
              T res(0);
              while (isdigit(ch)) res = res * 10 + (ch - '0'), ch = getc();
              return res;
            }
          void read() {}
          template <typename T, typename... U>
            void read(T& value, U&... args)
            { value = get<T>(), read(args...); }
        };
        class Printer {
          FILE* const stream; char buffer[BUFSIZ];
          char *head = buffer, *tail = 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() {
            head += fwrite(head, sizeof(char), tail - head, stream);
            memmove(buffer, head, sizeof(char) * (tail - head));
            tail -= head - buffer, head -= head - buffer;
            assert(head == tail);
          }
          public:
          void putc(char const ch) {
            if (tail == buffer + BUFSIZ) flush();
            assert(tail != buffer + BUFSIZ), *tail++ = ch;
          }
          void put(char const* s) { while (*s) putc(*s++); }
          template <typename T, enable_if_t<is_unsigned_v<T>, int> = 0>
            void put(T value) {
              static char stk[CHAR_BIT * sizeof(T)], *top(stk);
              while (*top++ = value % 10 + '0', value /= 10);
              while (putc(*--top), top != stk);
            }
          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;
                      default: assert(false); break;
                    }
                    break;
                  case 'z':
                    switch (*fmt++) {
                      case 'u': put(va_arg(args, size_t)); break;
                      default: assert(false); break;
                    }
                    break;
                  case 's': put(va_arg(args, char const*)); break;
                  case 'u': put(va_arg(args, uint)); break;
                  default: assert(false); break;
                }
              else putc(*fmt++);
            putc('\n');
            va_end(args);
          }
# define range_args InputIt const first, InputIt const last
# define split_args char const sep = ' ', char const end = '\n'
          template <class InputIt>
            void printrg(range_args, split_args) {
              for (InputIt i(first); i != last; advance(i, 1))
                put(*i), putc(next(i) == last ? end : sep);
            }
# undef range_args
# undef split_args
        };
      }
    }
    namespace b { void main(); }
    namespace c { void main(); }
  }
}

# endif

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

namespace khin::main::c {
  Scanner scanner; Printer printer;
  namespace test_case {
    constexpr uint Bmax(200), Smax(5'000);
    class FlowNetwork {
      struct Node { vector<uint> t; uint ht, cur; };
      struct Arc { uint t; uint cap; };
      uint n, m; Node v[2 * Bmax + 2]; Arc e[(2 * Bmax + Smax) << 1];
      bool bfs(uint const s, uint const t) {
        for (uint i(0); i < n; ++i) v[i].ht = ~0u, v[i].cur = 0;
        static uint q[2 * Bmax + 2]; auto head(q), tail(q);
        v[*tail++ = t].ht = 0;
        while (head != tail) {
          uint const x(*head++);
          for (uint const y : v[x].t)
            if (e[y ^ 1].cap && !~v[e[y].t].ht)
              v[*tail++ = e[y].t].ht = v[x].ht + 1;
        }
        /* fprintf(stderr, "BFS %u %u : %i\n", s, t, v[s].ht); */
        return ~v[s].ht;
      }
      uint dfs(uint const s, uint const t, uint flow = UINT_MAX) {
        if (s == t || !flow) return flow;
        uint res(0);
        for (uint& i(v[s].cur); i != v[s].t.size(); ++i) {
          uint const id(v[s].t[i]);
          if (e[id].cap && v[s].ht - v[e[id].t].ht == 1) {
            uint const r(dfs(e[id].t, t, min(flow, e[id].cap)));
            res += r, flow -= r, e[id ^ 1].cap += r, e[id].cap -= r;
            if (!flow) return res;
          }
        }
        return res;
      }
      public:
      void assign(uint const n) { this->n = n; }
      void clear() { fill(v, v + n, Node()), m = 0; }
      uint add(uint const s, uint const t, uint const cap = 1) {
        /* fprintf(stderr, "add %u %u %u\n", s, t, cap); */
        v[s].t.push_back(m), e[m++] = { t, cap };
        v[t].t.push_back(m), e[m++] = { s,   0 };
        return (m >> 1) - 1;
      }
      bool any(uint const index) const { return e[index << 1 | 1].cap; }
      uint max_flow(uint const s, uint const t) {
        uint flow(0);
        while (bfs(s, t)) {
          flow += dfs(s, t);
          /* fprintf(stderr, "flow : %u\n", flow); */
        }
        return flow;
      }
    };
    struct Building { vector<uint> s, t; uint S, T; bool vis; };
    struct Slide { uint u, v; uint index; };
    uint B, S; Building b[Bmax + 1]; Slide s[Smax];
    FlowNetwork net; vector<uint> z;
    void walk(uint const x) {
      while (!b[x].t.empty()) {
        uint const t(b[x].t.back());
        b[x].t.pop_back();
        walk(t), z.push_back(x);
      }
    }
    bool correct(uint const s, uint const t) {
      /* fprintf(stderr, "correct %u %u\n", s, t); */
      if (b[s].vis) return false; else b[s].vis = true;
      if (s == t) return true;
      for (uint const x : b[s].s)
        if (x != b[s].S && correct(b[x].T, t))
          return b[s].S = x, b[x].T = s, true;
      return false;
    }
    void main(ushort const x) {
      /* fprintf(stderr, "running on test %hu\n", x); */
      scanner.read(B, S), net.assign(2 * B + 2);
      for (uint i(1); i <= B; ++i)
        net.add(0, i + 1), net.add(i + B + 1, 1);
      for (uint i(0); i < S; ++i) {
        scanner.read(s[i].u, s[i].v);
        b[s[i].v].s.push_back(s[i].u);
        s[i].index = net.add(s[i].u + 1, s[i].v + B + 1);
      }
      if (net.max_flow(0, 1) < B) {
        printer.println("Case #%hu: %s", x, "IMPOSSIBLE");
        fill(b + 1, b + B + 1, Building()), net.clear();
        return;
      }
      for (uint i(0); i < S; ++i) if (net.any(s[i].index))
        b[s[i].u].T = s[i].v, b[s[i].v].S = s[i].u;
      for (uint i(0); i < S; ++i) {
        /* fprintf(stderr, "try %u %u\n", s[i].u, s[i].v); */
        if (correct(b[s[i].u].T, s[i].v)) {
          for (uint j(1); j <= B; ++j) b[j].vis = false;
          b[s[i].u].T = s[i].v, b[s[i].v].S = s[i].u;
          for (uint j(1); j <= B; ++j) b[j].t.push_back(b[j].T);
        } else {
          printer.println("Case #%hu: %s", x, "IMPOSSIBLE");
          fill(b + 1, b + B + 1, Building()), net.clear();
          return;
        }
      }
      walk(1), reverse(z.begin(), z.end()), z.push_back(1);
      for (uint i(1); i <= B; ++i) if (!b[i].t.empty()) {
        printer.println("Case #%hu: %s", x, "IMPOSSIBLE");
        fill(b + 1, b + B + 1, Building()), net.clear(), z.clear();
        return;
      }
      printer.println("Case #%hu: %zu", x, z.size());
      printer.printrg(z.begin(), z.end()), z.clear();
      fill(b + 1, b + B + 1, Building()), net.clear();
    }
  }
  void main() {
    ushort const T(scanner.get<ushort>());
    for (ushort i(1); i <= T; ++i) test_case::main(i);
  }
}