有向图,有环就输出impossibol
没有环就按字典序拓扑排序,
用map映射字符串和点的下标
判环可以tarjan或直接dfs
我这里用tarjan练手了

#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)3e4+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \
    do { \
        cout << "\033[31;1m " << #x << " -> "; \
        err(x); \
    } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#endif

namespace FastIO{

    char print_f[105];
    void read() {}
    void print() { putchar('\n'); }

    template <typename T, typename... T2>
        inline void read(T &x, T2 &... oth) {
            x = 0;
            char ch = getchar();
            ll f = 1;
            while (!isdigit(ch)) {
                if (ch == '-') f *= -1; 
                ch = getchar();
            }
            while (isdigit(ch)) {
                x = x * 10 + ch - 48;
                ch = getchar();
            }
            x *= f;
            read(oth...);
        }
    template <typename T, typename... T2>
        inline void print(T x, T2... oth) {
            ll p3=-1;
            if(x<0) putchar('-'), x=-x;
            do{
                print_f[++p3] = x%10 + 48;
            } while(x/=10);
            while(p3>=0) putchar(print_f[p3--]);
            putchar(' ');
            print(oth...);
        }
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int n, m, Q, K, ind[MAXN], tot, ans, vis[MAXN];

string s[MAXN];

vector<int> G[MAXN];
map<string, int> mp;

int ID(string str) {
    int& rx = mp[str];
    if(!rx) rx = ++ tot;
    return rx;
}

int instk[MAXN], timer, low[MAXN], dfn[MAXN], sig/**强连通分量个数*/, hasCle, cas;

void init() {
    printf("Case #%d:\n", ++cas);
    tot = 0;
    mp.clear();
    memset(ind, 0, sizeof(ind));
    memset(vis, 0, sizeof(vis));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(instk, 0, sizeof(instk));
    for(int i=1; i<=MAXN-3; i++) G[i].clear();
    hasCle = sig = timer = ans = 0;
}

stack<int> stk;
void tarjan(int u) {
    instk[u] = 1;
    stk.push(u);
    dfn[u] = low[u] = ++timer;
    for(auto v : G[u]) {
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if(instk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        hasCle = true;
        int x = 0;
        sig ++;
        while(x != u) {
            x = stk.top(); stk.pop();
            instk[x] = 0;
        }
    }
}

void topsort() {
    priority_queue<int, vector<int>, greater<int> > q;
    for(int i=1; i<=n; i++)
        if(!ind[i]) q.push(i);
    while(!q.empty()) {
        auto now = q.top(); q.pop();
        printf("%s\n", s[now].data());
        vis[now] = true;
        for(auto v : G[now]) {
            ind[v] --;
            if(ind[v] == 0 && !vis[v]) q.push(v), vis[v] = true;
        }
    }
}

int main() {
#ifdef debug
    freopen("test", "r", stdin);
    clock_t stime = clock();
#endif
    scanf("%d ", &Q);
    while(Q--) {
        init();
        scanf("%d %d ", &n, &m);
//        show(n, m);
        char buf[128], buf2[128];
        for(int i=1; i<=n; i++) {
            scanf("%s ", buf);
            s[i] = buf;
        }
        sort(s+1, s+1+n); //先把字符串排序 再去映射下标 多此一举
        for(int i=1; i<=n; i++) 
            ID(s[i]);



        for(int i=1; i<=m; i++) {
            scanf("%s %s ", buf, buf2);
            int u = ID(buf), v = ID(buf2); //映射下标
            G[u].push_back(v);
            ind[v] ++; //入度++
        }
        for(int i=1; i<=tot; i++)
            if(!dfn[i]) tarjan(i);
        if(sig < n) { //如果图绝对无环,则强连通分量个数应该是n
            printf("Impossible\n");
            continue ;
        }
        topsort();
    }



#ifdef debug
    clock_t etime = clock();
    printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
    return 0;
}