#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct vertex
{
    vector<int> neighbours;
    vector<int> results;
};

bool ifEdge(vector<vertex>& g, int v, int w)
{
    if (find(g[v].neighbours.begin(), g[v].neighbours.end(), 0) != g[v].neighbours.end())
        return true;
    else
        return false;
}

void input(vector<vertex>& g)
{
    int n, m;
    cin >> n >> m;

    g.assign(n + 1, vertex());

    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;

        g[a].neighbours.push_back(b);
        g[b].neighbours.push_back(a);
    }
}

bool solve(vector<vertex>& g, stack<int>& st, vector<bool>& r, int s, int v)
{
    st.push(v);

    if (st.size() == g.size())
        if (ifEdge(g, v, 0))
            return r[v] = true;
        else
            return r[v] = false;

    for (int i = 0; i < g[v].neighbours.size(); i++)
        if ((1 << g[v].neighbours[i]) & s)
            if (ifEdge(g, v, g[v].neighbours[i]) && solve(g, st, r, s - (1 << g[v].neighbours[i]), g[v].neighbours[i]))
                return r[v] = true;

    st.pop();

    return r[v] = false;
}

void output(stack<int>& s)
{
    while (!s.empty())
    {
        if (s.top() != 0)
            cout << s.top() << " ";

        s.pop();
    }

    cout << endl;
}

int main()
{
    int z;
    cin >> z;

    while (z--)
    {
        vector<vertex> graph;
        stack<int> stackOut;
        vector<bool> results;
        int s;

        input(graph);

        s = 1 << (graph.size() + 1) - 1;
        results.assign(graph.size(), 0);

        bool res = solve(graph, stackOut, results, s - 1, 0);

        if (res)
        {
            cout << "TAK" << endl;
            output(stackOut);
        }
        else
            cout << "NIE" << endl;
}

    return 0;
}