OI XXVIII - zdj (Jiangly)

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

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

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

    std::vector<std::vector<int>> adj(n);
    std::vector<int> deg(n);

    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 0; i < n; i++) {
        deg[i] = adj[i].size() / 2;
    }

    for (auto v : adj[0]) {
        deg[v]--;
    }

    int cur = 1;

    std::queue<int> q;

    for (int i = 2; i < n; i++) {
        if (deg[i] == 0) {
            q.push(i);
        }
    }

    std::vector<int> h(n, -1);
    h[0] = 0;
    h[1] = n - 1;

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

        h[u] = cur++;

        if (deg[u] != 0) {
            std::cout << "NIE\n";
            return 0;
        }

        for (auto v : adj[u]) {
            if (h[v] == -1 && --deg[v] == 0) {
                q.push(v);
            }
        }
    }

    if (cur < n - 1) {
        std::cout << "NIE\n";
        return 0;
    }

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

    for (int i = 0; i < n; i++) {
        std::cout << h[i] + 1 << " \n"[i == n - 1];
    }

    return 0;
}