#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, m, fa[maxn << 1];
int h[maxn << 1], cntt = 1;
bool vis[maxn << 1];
struct Node
{
    int to, nxt;
} e[maxn << 2];
void Add(int u, int v)
{
    e[++cntt].nxt = h[u];
    h[u] = cntt;
    e[cntt].to = v;
}
void dfs(int u)
{
    vis[u] = true;
    for (int i = h[u]; i; i = e[i].nxt)
    {
        if (i != fa[u])
        {
            int v = e[i].to;
            if (!vis[v])
                fa[v] = i ^ 1, dfs(v);
            else
            {
                vector<int> ways{i};
                for (int x = u; x != v; x = e[fa[x]].to)
                {
                    ways.push_back(fa[x]);
                }
                cout << "Tak\n" << ways.size() << '\n';
                for (auto z : ways)
                    cout << z / 2 << ' ';
                cout << "\n";
                exit(0);
            }
        }
    }
}
bool dag[maxn << 1];
vector<int> ways;
void dfs2(int u)
{
    vis[u] = true;
    for (int i = h[u]; i; i = e[i].nxt)
    {
        if (i ^ fa[u])
            dfs2(e[i].to);
    }
    if (fa[u] and !dag[u])
    {
        dag[e[fa[u]].to] ^= 1;
        ways.push_back(fa[u]);
        dag[u] ^= 1;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        Add(x, y);
        Add(y, x);
    }
    for (int i = 1; i <= 2 * n; i++)
    {
        if (!vis[i])
            dfs(i);
    }
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= (n << 1); i++)
    {
        dfs2(i);
        if (!dag[i])
        {
            cout << "NIE\n";
            return 0;
        }
        cout << "TAK\n" << ways.size() << "\n";
        for (auto z : ways)
            cout << z / 2 << ' ';
        cout << "\n";
    }
    return 0;
}