假设原图不存在孤点。

权值为 $1$ 的点一定是 $1$ 号或 $2$ 号，否则一定有至少一个与其相邻的点权值比 $1$ 更小，但这显然不可能。

权值为 $n$ 的点同理。

我们钦定 $h _ 1 = 1$，$h _ 2 = n$。如果存在一组解中 $h _ 1 = n$，那么将所有 $h _ i$ 变为 $n - h _ i + 1$ 即可调整得 $h _ 1 = 1$。

假设解存在。那么可以在图上，按照 $h _ i$ 的大小顺序遍历每个点。设当前遍历到 $u(u > 2)$ 号点，其度数为 $deg _ u$，那么在与 $u$ 相邻的点中，一定有恰好 $\frac {deg _ u} 2$ 个点被遍历过，它们的权值 $< h _ u$；剩下恰好 $\frac {deg _ u} 2$ 个点没有被遍历过，它们的权值 $> h _ u$。

这启发我们用一个类似拓扑排序的过程来求出一组 $h$。维护一个队列。初始时，将所有与 $1$ 号相邻并且度数恰为 $2$ 的点加入队列。对于第 $i$ 个出队的点 $u$，令 $h _ u = i + 1$，然后将其从图中删掉。访问所有删掉 $u$ 之前与 $u$ 相邻的点 $v$，设删除 $u$ 后 $v$ 的度数为 $d _ v$，若 $2 d _ v = deg _ v$，这意味着 $v$ 已经有恰好 $\frac {deg _ v} 2$ 个相邻的点被遍历过，这时可以将 $v$ 加入队列。

如果这样的遍历不能完全进行，即除了 $1$ 号和 $2$ 号以外，还有点没有入过队，那么无解；如果 $u$ 出队时，$2 d _ u \neq deg _ u$，这不满足遍历 $u$ 时恰有 $\frac {deg _ u} 2$ 个相邻点被遍历过，也无解。

若原图存在孤点，它们的权值也可以为 $1$ 或 $n$，但这并不影响。给他们随便赋几个值，剩下的部分是一样的。

时间复杂度 $O(n)$，实现有一些细节。

#include <bits/stdc++.h>
#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define dF(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, LL> pii;
const int N = 5e5 + 5;

int n, m, deg[N], h[N]; vector<int> e[N];

int main() {
  // freopen("zyq.in", "r", stdin);
  // freopen("zyq.out", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  F(i, 1, m) {
    int u, v; cin >> u >> v;
    e[u].push_back(v), e[v].push_back(u);
    ++deg[u], ++deg[v];
  }
  F(i, 3, n) deg[i] >>= 1;
  h[1] = 1, h[2] = n;
  queue<int> q; int now = 1;
  F(i, 3, n) if (!deg[i]) h[i] = ++now;
  for (auto v : e[1]) --deg[v];
  F(i, 3, n) if (!h[i] && !deg[i]) q.push(i);
  while (!q.empty()) {
    int u = q.front(); q.pop(), h[u] = ++now;
    if (deg[u]) return cout << "NIE\n", 0;
    for (auto v : e[u]) if (!h[v] && !(--deg[v])) q.push(v);
  }
  if (now < n - 1) return cout << "NIE\n", 0;
  cout << "TAK\n";
  F(i, 1, n) cout << h[i] << " ";
  return 0;
}