// https://szkopul.edu.pl/problemset/problem/ptF7RsWMiiMdzzZWt5BKFAnT/site/?key=statement
// OI XV (1 etap)

// Cło

#include <bitset>
#include <iostream>
#include <vector>

constexpr int sizik = 100 * 1001;

std::vector<int> kra[sizik];

int ans[sizik];
int dep[sizik];

// std::bitset<sizik> visited;
short visited[sizik];

int helper = 1;
int result = -1;
int akt = 0;
int p, k;
bool isGood;

void DFS1(int v, int o) {
    if (visited[v] == akt || v == 0) {
        return;
    }

    visited[v] = akt;

    for (int i = 0; i < kra[v].size(); i++) {
        const auto r = kra[v][i];

        if (r != o) {
            if (visited[r] == akt) {
                p = v;
                k = r;
                isGood = true;

                for (int j = 0; j < kra[p].size(); j++) {
                    if (kra[p][j] == k) {
                        std::swap(kra[p][j], kra[p].back());
                        kra[p].pop_back();
                        break;
                    }
                }
                for (int j = 0; j < kra[k].size(); j++) {
                    if (kra[k][j] == p) {
                        std::swap(kra[k][j], kra[k].back());
                        kra[k].pop_back();
                        break;
                    }
                }
            } else {
                DFS1(r, v);
            }
        }
    }
}

void DFS2(int v, int o) {
    if (visited[v] == akt || v == 0) {
        return;
    }

    visited[v] = akt;
    if (o != -1 && ans[v] == 0) {
        ans[v] = o;
    }

    for (const auto& r : kra[v]) {
        if (visited[r] != akt) {
            DFS2(r, v);
        }
    }
}

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

    int n, m;
    std::cin >> n >> m;

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

        kra[a].push_back(b);
        kra[b].push_back(a);

        dep[a]++;
        dep[b]++;
    }

    for (int i = 1; i <= n; i++) {
        if (ans[i] != 0) {
            continue;
        }

        helper = i;
        akt++;
        isGood = false;
        DFS1(i, -1);

        if (isGood == false) {
            std::cout << "NIE\n";
            return 0;
        }

        ans[p] = k;

        akt++;
        DFS2(p, -1);
    }

    std::cout << "TAK\n";

    for (int i = 1; i <= n; i++) {
        std::cout << ans[i] << '\n';
    }

    return 0;
}