// https://szkopul.edu.pl/problemset/problem/eQ4z7Bnhqsl67nKb_NlISLNZ/site/?key=statement

#include <bits/stdc++.h>

using namespace std;

constexpr int sizik = 1000 * 1001;
constexpr int sizik2 = 500 * 1001;
constexpr int sizik3 = 100 * 1001;

#define ar std::array
#define pr std::pair
#define vec std::vector

#define ca const auto

typedef long long ll;
typedef vec<vec<int>> _kra;

struct Guzik {
    int x, y;
    Guzik(int x1 = 0, int y1 = 0) { x = x1, y = y1; }
};

ar<int, sizik> we;
int n, m;

ar<Guzik, sizik2> bG;

std::map<pr<int, int>, int> Gi_;

ar<std::vector<int>, sizik3> mpv, mpv2;

std::bitset<sizik> visited, visited2, visited3, visited4, visited5, visited7, visited8;

ar<vec<int>, sizik> kra;
ar<std::vector<int>, sizik3> FF_R, FF_C;

int R[sizik3], C[sizik3];

bool Found = false;

void DFS(int v, int k, int p) {
    if (visited4[v]) {
        return;
    }

    visited4[v] = true;

    for (const auto& u : kra[v]) {
        if (u != p && !visited3[u]) {
            DFS(u, k + 1, v);
        }
    }
}

int visited6[sizik];
int GLOBAL_BFS_COUNTER = 1;
int BFS_TRACE[sizik];

void BFS(int p, int k, int z) {
    std::queue<ar<int, 2>> q;
    q.push({p, p});

    while (!q.empty()) {
        const auto [d, par] = q.front();
        q.pop();

        if (visited6[d] == z) {
            continue;
        }

        visited6[d] = z;
        BFS_TRACE[d] = par;

        for (const auto& u : kra[d]) {
            q.push({u, d});
        }
    }
}

void backtrack_BFS(int p, int k, std::vector<int>& res) {
    int x = k;

    while (BFS_TRACE[x] != p) {
        x = BFS_TRACE[x];
        res.push_back(x);
    }
}

int looker_DFS1_helper = -1, DFS1_p2 = -1;
bool found_DFS1_helper = false;
void DFS1(int v, int p1, int p2) {
    if (found_DFS1_helper) {
        return;
    }

    if (visited7[v]) {
        if (v == looker_DFS1_helper) {
            DFS1_p2 = p2;
            found_DFS1_helper = true;
        }
        return;
    }

    visited7[v] = true;

    for (const auto& u : kra[v]) {
        if (u != p1) {
            DFS1(u, v, p1);
        }
    }
}

ar<int, sizik> disc, low;
int time1 = 0;
vec<ar<int, 2>> bridges;

void BridgeDFS(int u, int p) {
    visited5[u] = true;

    disc[u] = ++time1;
    low[u] = disc[u];

    for (const auto& v : kra[u]) {
        if (v == p) continue;

        if (visited5[v]) {
            low[u] = std::min(low[u], disc[v]);
        } else {
            BridgeDFS(v, u);

            low[u] = min(low[u], low[v]);

            if (low[v] > disc[u]) {
                bridges.push_back({u, v});
            }
        }
    }
}

int depth_DFS3[sizik], parent_DFS3[sizik], count_DFS3 = 0;
void DFS3(int v, int p, int d) {
    depth_DFS3[v] = d;
    parent_DFS3[v] = p;
    count_DFS3++;

    for (const auto& u : kra[v]) {
        if (u != p) {
            DFS3(u, v, d + 1);
        }
    }
}

std::vector<int> ans_DFS4;
void DFS4(int v, int p) {
    if (v != p) {
        int x = v, y = p - n;
        if (v > p) {
            x = p, y = v - n;
        }

        ans_DFS4.push_back(Gi_[{x, y}]);
    }

    visited8[v] = true;

    for (const auto& u : kra[v]) {
        if (u != p) {
            DFS4(u, v);
        }
    }
}

void print_btn(int z, bool nl = true);
void brut(int n, int m);

void solve() {
    std::cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y;
        std::cin >> x >> y;

        mpv[x].push_back(y);
        mpv2[y].push_back(x);

        bG[i + 1] = {x, y};
        Gi_[{x, y}] = i + 1;
    }

    for (int i = 1; i <= n; i++) {
        std::sort(mpv[i].begin(), mpv[i].end());
        std::sort(mpv2[i].begin(), mpv2[i].end());
    }

    int dbg = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < mpv[i].size(); j++) {
            if (j != 0) {
                kra[Gi_[{i, mpv[i][j]}]].push_back(Gi_[{i, mpv[i][j - 1]}]);
            }
            if (j != (int)mpv[i].size() - 1) {
                kra[Gi_[{i, mpv[i][j]}]].push_back(Gi_[{i, mpv[i][j + 1]}]);
            }
        }

        for (int j = 0; j < mpv2[i].size(); j++) {
            if (j != 0) {
                kra[Gi_[{mpv2[i][j], i}]].push_back(Gi_[{mpv2[i][j - 1], i}]);
            }
            if (j != (int)mpv2[i].size() - 1) {
                kra[Gi_[{mpv2[i][j], i}]].push_back(Gi_[{mpv2[i][j + 1], i}]);
            }
        }
    }

    std::queue<int> q;
    for (int i = 1; i <= m; i++) {
        ca d = kra[i].size();
        we[i] = d;

        if (d == 1) {
            q.push(i);
        } else if (d == 0) {
            visited2[i] = true;
        }
    }

    while (!q.empty()) {
        int z = q.front();
        q.pop();

        if (visited2[z]) {
            continue;
        }

        visited2[z] = true;

        for (const auto& s : kra[z]) {
            if (--we[s] <= 1) {
                q.push(s);
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        if (!visited2[i]) {
            Found = true;
        }
    }

    for (int i = 0; i < kra.size(); i++) {
        kra[i].clear();
    }

    if (Found) {
        std::cout << "TAK\n";

        for (int i = 1; i <= m; i++) {
            if (!visited2[i]) {
                const auto [x, y] = bG[i];
                // kra2[x].push_back(y + n);
                kra[x].push_back(y + n);
                // kra2[y + n].push_back(x);
                kra[y + n].push_back(x);
            }
        }

        for (int i = 1; i <= 2 * n; i++) {
            std::sort(kra[i].begin(), kra[i].end());
        }

        std::queue<int> q1;
        for (int i = 1; i <= 2 * n; i++) {
            ca d = kra[i].size();
            we[i] = d;

            if (d == 1) {
                q1.push(i);
            } else if (d == 0) {
                visited3[i] = true;
            }
        }

        while (!q1.empty()) {
            int z = q1.front();
            q1.pop();

            if (visited3[z]) {
                continue;
            }

            visited3[z] = true;

            for (const auto& s : kra[z]) {
                if (--we[s] <= 1) {
                    q1.push(s);
                }
            }
        }

        for (int i = 1; i <= 2 * n; i++) {
            if (visited3[i]) {
                kra[i].clear();
            }
        }

        for (int i = 1; i <= 2 * n; i++) {
            if (kra[i].size() < 1) {
                visited3[i] = true;
            }
        }

        for (int i = 1; i <= n; i++) {
            if (!visited3[i]) {
                BridgeDFS(i, i);
                break;
            }
        }

        for (const auto& [a, b] : bridges) {
            auto ptr = std::lower_bound(kra[a].begin(), kra[a].end(), b);
            if (ptr != kra[a].end() && *ptr == b) {
                kra[a].erase(ptr);
            }

            auto ptr1 = std::lower_bound(kra[b].begin(), kra[b].end(), a);
            if (ptr1 != kra[b].end() && *ptr1 == a) {
                kra[b].erase(ptr1);
            }
        }

        bridges.clear();

        for (int i = 1; i <= 2 * n; i++) {
            if (kra[i].size() < 1) {
                visited3[i] = true;
            }
        }

        int po = -1, ko = -1;

        for (int i = 1; i <= n; i++) {
            if (!visited3[i] && !visited7[i]) {
                po = i;

                looker_DFS1_helper = po;
                DFS1(po, po, po);

                ko = DFS1_p2;
                break;
            }
        }

        BFS(po, ko, ++GLOBAL_BFS_COUNTER);

        std::vector<int> part_ans1, part_ans2;
        backtrack_BFS(po, ko, part_ans1);

        ++GLOBAL_BFS_COUNTER;
        for (const auto& a : part_ans1) {
            if (a != po && a != ko) {
                visited6[a] = GLOBAL_BFS_COUNTER;
            }
        }

        BFS(po, ko, GLOBAL_BFS_COUNTER);
        backtrack_BFS(po, ko, part_ans2);

        part_ans1.push_back(po);
        part_ans2.push_back(po);

        pr<int, int> temp{ko, 0};

        std::vector<int> REAL_ANS;

        for (const auto& a : part_ans1) {
            if (a > n) {
                temp.second = a - n;
            } else {
                temp.first = a;
            }

            REAL_ANS.push_back(Gi_[temp]);
        }

        temp = {ko, 0};

        for (const auto& a : part_ans2) {
            if (a > n) {
                temp.second = a - n;
            } else {
                temp.first = a;
            }

            REAL_ANS.push_back(Gi_[temp]);
        }

#ifndef NO_ANS
        std::cout << REAL_ANS.size() << '\n';
        for (const auto& a : REAL_ANS) {
            std::cout << a << " ";
        }
        std::cout << '\n';
#endif

        return;
    }

    for (int i = 1; i <= n; i++) {
        if (mpv[i].size() == 0 || mpv2[i].size() == 0) {
            std::cout << "NIE\n";
            return;
        }
    }

    for (int i = 1; i <= m; i++) {
        const auto [x, y] = bG[i];
        kra[x].push_back(y + n);
        kra[y + n].push_back(x);
    }

    bool isGood_HERE = true;

    for (int i = 1; i <= 2 * n; i++) {
        if (depth_DFS3[i] == 0) {
            count_DFS3 = 0;
            DFS3(i, i, 1);

            if (count_DFS3 % 2 == 1) {
                isGood_HERE = false;
                break;
            }
        }
    }

    if (!isGood_HERE) {
        std::cout << "NIE\n";
        return;
    }

    std::vector<int> v_NP;
    for (int i = 1; i <= 2 * n; i++) {
        v_NP.push_back(i);
        we[i] = kra[i].size();
    }

    for (int i = 1; i <= 2 * n; i++) {
        std::sort(kra[i].begin(), kra[i].end());
    }

    std::sort(v_NP.begin(), v_NP.end(), [](int a, int b) { return depth_DFS3[a] > depth_DFS3[b]; });

    for (const auto& z : v_NP) {
        if (we[z] % 2 == 0) {
            we[z]--;
            we[parent_DFS3[z]]--;

            auto ptr = std::lower_bound(kra[z].begin(), kra[z].end(), parent_DFS3[z]);
            if (ptr != kra[z].end() && *ptr == parent_DFS3[z]) {
                kra[z].erase(ptr);
            }

            auto ptr1 = std::lower_bound(kra[parent_DFS3[z]].begin(), kra[parent_DFS3[z]].end(), z);
            if (ptr1 != kra[parent_DFS3[z]].end() && *ptr1 == z) {
                kra[parent_DFS3[z]].erase(ptr1);
            }
        }
    }

    for (int i = 1; i <= 2 * n; i++) {
        if (!visited8[i]) {
            DFS4(i, i);
        }
    }

    std::cout << "TAK\n";
#ifndef NO_ANS
    std::cout << ans_DFS4.size() << '\n';
    for (const auto& a : ans_DFS4) {
        std::cout << a << ' ';
    }
    std::cout << '\n';
#endif
}

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

    int t = 1;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}

void print_btn(int z, bool nl) {
    std::cout << z << " [ " << bG[z].x << " , " << bG[z].y << " ]";
    if (nl) std::cout << endl;
}

void brut(int n, int m) {
    std::vector<Guzik> v(m);

    for (int i = 1; i <= m; i++) {
        v[i - 1].x = bG[i].x;
        v[i - 1].y = bG[i].y;
    }

    for (int i = 1; i < (1 << m); i++) {
        std::vector<int> R(n + 1, 0), C(n + 1, 0), pt_ans;
        int temp_i = i;

        for (int j = 0; j < m; j++) {
            if (temp_i % 2 == 1) {
                const auto& b = v[j];
                R[b.y]++;
                C[b.x]++;

                pt_ans.push_back(j + 1);
            }

            temp_i >>= 1;
        }

        int chk = R[1] % 2;
        bool isGood = true;
        for (int j = 1; j <= n; j++) {
            if ((R[j] % 2) != chk) {
                isGood = false;
                break;
            }
            if ((C[j] % 2) != chk) {
                isGood = false;
                break;
            }
        }

        if (isGood) {
            std::cout << "TAK\n";
            std::cout << pt_ans.size() << '\n';
            for (const auto& a : pt_ans) {
                std::cout << a << ' ';
            }
            std::cout << '\n';
            return;
        }
    }

    std::cout << "NIE\n";
}