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

using namespace std;

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

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, unordered_map<int, unordered_map<int, bool>>& r, int s, int v)
{
    for (int i = 0; i < g[v].neighbours.size(); i++)
    {
        if (st.size() == g.size() && g[v].neighbours[i] == 0)
            return true;

        int x = s | (1 << g[v].neighbours[i]);

        if (s != x && r[g[v].neighbours[i]].find(x) == r[g[v].neighbours[i]].end())
        {
            st.push(g[v].neighbours[i]);

            if (solve(g, st, r, x, g[v].neighbours[i]))
                return true;
            else
            {
                st.pop();
                r[g[v].neighbours[i]][x] = false;
            }
        }
    }

    return 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;
        unordered_map<int, unordered_map<int, bool>> visited;
        stack<int> stackOut;

        input(graph);

        bool res = solve(graph, stackOut, visited, 1, 0);

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

    return 0;
}