#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <cstdio>
#include <string>
#include <vector>
namespace iobuff {
const int LEN = 1000000;
char in[LEN + 5], out[LEN + 5];
char *pin = in, *pout = out, *ed = in, *eout = out + LEN;
inline char gc(void) {
return pin == ed && (ed = (pin = in) + fread(in, 1, LEN, stdin), ed == in) ? EOF : *pin++;
}
inline void pc(char c) {
pout == eout && (fwrite(out, 1, LEN, stdout), pout = out);
(*pout++) = c;
}
inline void ps(const std::string &s) {
for (auto c : s)
pc(c);
}
inline void flush() { fwrite(out, 1, pout - out, stdout), pout = out; }
template <typename T>
inline void scan(T &x) {
static int f;
static char c;
c = gc(), f = 1, x = 0;
while (c < '0' || c > '9')
f = (c == '-' ? -1 : 1), c = gc();
while (c >= '0' && c <= '9')
x = 10 * x + c - '0', c = gc();
x *= f;
}
template <typename T>
inline void putint(T x, char div) {
static char s[100];
static int top;
top = 0;
x < 0 ? pc('-'), x = -x : 0;
while (x)
s[top++] = x % 10, x /= 10;
!top ? pc('0'), 0 : 0;
while (top--)
pc(s[top] + '0');
pc(div);
}
}
using namespace iobuff;
int main() {
int T;
scan(T);
for (int TC = 1; TC <= T; TC++) {
ps("Case #"), putint(TC, ':'), pc(' ');
int n, m;
scan(n), scan(m);
std::vector<std::vector<int>> ed(n), rved(n);
for (int i = 0; i < m; i++) {
int u, v;
scan(u), scan(v);
ed[--u].push_back(--v);
rved[v].push_back(u);
}
std::vector<bool> con1(n), con2(n);
bool imp = 0;
int lst;
auto scc1 = [&](const auto &scc1, int u) -> void {
con1[u] = 1;
for (auto v : ed[u])
if (!con1[v])
scc1(scc1, v);
lst = u;
};
scc1(scc1, 0);
for (int i = 0; i < n; i++) {
if (!con1[i]) {
imp = 1;
break;
}
}
auto scc2 = [&](const auto &scc2, int u) -> void {
con2[u] = 1;
for (auto v : rved[u])
if (!con2[v])
scc2(scc2, v);
};
scc2(scc2, lst);
for (int i = 0; i < n; i++) {
if (!con2[i]) {
imp = 1;
break;
}
}
if (imp) {
ps("IMPOSSIBLE\n");
continue;
}
std::vector<int> lnk(n, -1), vis(n, 0);
auto dfs = [&](const auto &dfs, const int &u, std::vector<bool> &vis) -> bool {
for (int v : ed[u]) {
if (vis[v])
continue;
vis[v] = 1;
if (!~lnk[v] || dfs(dfs, lnk[v], vis)) {
lnk[v] = u;
return true;
}
}
return false;
};
int cnt = 0;
for (int i = 0; i < n; i++) {
std::vector<bool> vis(n, 0);
if (dfs(dfs, i, vis))
cnt++;
}
if (cnt < n) {
ps("IMPOSSIBLE\n");
continue;
}
// begin
std::vector<std::vector<int>> nwed(n);
for (int u = 0; u < n; u++) {
if (imp)
break;
for (auto v : ed[u]) {
if (lnk[v] == u) {
for (int i = 0; i < n; i++) {
nwed[lnk[i]].push_back(i);
}
continue;
}
for (int i = 0; i < n; i++)
if (lnk[i] == u)
lnk[i] = -1;
int tmp = lnk[v];
lnk[v] = u;
std::vector<bool> vis(n, 0);
vis[v] = 1;
if (!dfs(dfs, tmp, vis)) {
imp = 1;
break;
}
for (int i = 0; i < n; i++) {
nwed[lnk[i]].push_back(i);
}
}
}
if (imp) {
ps("IMPOSSIBLE\n");
continue;
}
// end
putint( n * m + 1 , '\n');
std::vector<int> ans;
auto fnd = [&](const auto &fnd, const int &u) -> void {
for (auto &x : nwed[u]) {
int v = x;
if (!~v)
continue;
x = -1;
fnd(fnd, v);
ans.push_back(u);
}
};
fnd(fnd, 0);
int st = 0;
for (; ans[st] != 0; st++)
;
for (int i = st; ~i; i--) {
putint(ans[i]+1, ' ');
}
for (int i = n * m - 1; i > st; i--) {
putint(ans[i]+1, ' ');
}
ps("1\n");
}
flush();
}