#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

const int MOD = 1e9 + 1000 - 7, B = 5757;

int add(int a, int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}

int mul(int a, int b) {
    return (1ll * a * b) % MOD;
}

struct Node {
    int h0, h1;
    int par;
    int symb;

    Node(int par = -1, int symb = -1): h0(0), h1(0), par(par), symb(symb) {}
};

const int MAXMEM = 1e7 + 100;
Node nd[MAXMEM];
int id_nd = 0;

int nn(int par = -1, int symb = -1) {
    nd[id_nd] = Node(par, symb);
    return id_nd++;
}

int push(int v, int ch) {
    int u = nn(v, ch);
    nd[u].h0 = add(ch, mul(nd[v].h0, B));
    if (nd[v].par != -1) {
        nd[u].h1 = add(ch, mul(nd[v].h1, B));
    }
    return u;
}

string restore(int v) {
    string ans;
    while (nd[v].par != -1) {
        ans.push_back(nd[v].symb + 'a');
        v = nd[v].par;
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

int get_pref(int v) {
    return nd[nd[v].par].h0;
}

int get_suf(int v) {
    return nd[v].h1;
}

const int MAXN = 1e6 + 100;
vector<int> g[MAXN];
vector<int> var[MAXN];
int used[MAXN];

int last_letter;

int rt = nn();

void dfs(int v) {
    used[v] = true;
    for (int u : g[v]) {
        if (!used[u]) {
            dfs(u);
        }
    }
    if (g[v].empty()) {
        var[v] = {push(rt, last_letter++)};
        return;
    }
    if ((int)g[v].size() == 1) {
        int u = var[g[v][0]][0];
        var[v] = {push(u, nd[u].symb)};
        return;
    }
    int a = g[v][0], b = g[v][1];
    for (int i = 0; i < 2; ++i, swap(a, b)) {
        unordered_set<int> hsh;
        for (int p : var[a]) {
            for (int q : var[b]) {
                if (get_suf(p) == get_pref(q)) {
                    int r = push(p, nd[q].symb);
                    if (!hsh.count(nd[r].h0)) {
                        hsh.insert(nd[r].h0);
                        var[v].push_back(r);
                    }
                }
            }
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        g[i].clear();
    }
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[v].push_back(u);
    }
    fill(var, var + n, vector<int>());
    fill(used, used + n, 0);
    for (int i = 0; i < n; ++i) {
        for (int u : g[i]) {
            used[u] = true;
        }
    }
    int rt = -1;
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            rt = i;
        }
    }
    fill(used, used + n, 0);
    last_letter = 0;
    dfs(rt);
    string ans;
    for (int v : var[rt]) {
        string s = restore(v);
        map<char, char> opt;
        int lst = 0;
        string t;
        for (auto ch : s) {
            if (!opt.count(ch)) {
                opt[ch] = 'a' + (lst++);
            }
            t.push_back(opt[ch]);
        }
        if (ans.empty() || t < ans) {
            ans = t;
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }

    return 0;
}