OI XXVIII - zdj (Alt)

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

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 500010
#define pb emplace_back
#define szi sizeof(int)
#define il inline
int n, m, a[N], cnt = 0, d[N], x, y, in[N];
vector<int> g[N];
queue<int> q;
signed main() {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &x, &y), g[x].pb(y), g[y].pb(x);
        ++in[x], ++in[y];
    }

    for (int i = 3; i <= n; ++i)
        in[i] >>= 1;

    in[1] = 0;

    for (int i = 1; i <= n; ++i)
        if (!in[i]) q.push(i);

    while (q.size()) {
        int x = q.front();
        a[x] = ++cnt, q.pop();

        for (int y : g[x])
            if (!a[y]) {
                --in[y];

                if (in[y] < 0) return puts("NIE"), 0;

                if (!in[y]) q.push(y);
            }
    }

    if (cnt < n) return puts("NIE"), 0;

    puts("TAK");

    for (int i = 1; i <= n; ++i)
        printf("%d ", a[i]);

    puts("");
    return 0;
}