题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXVIII Olimpiada Informatyczna – II etap Zdjęcia krasnali

在新年派对上，有 $n$ 个小矮人在玩耍。为了让这次派对留下美好的回忆，小矮人们请来了一位摄影师，要为每个小矮人和他的朋友们拍一张合影。每个小矮人（除了 Gburk 和 Wesołek，他们俩无所谓，但原因各不相同）都希望在自己的照片中站在正中间。幸运的是，每个小矮人的朋友数量都是偶数。

但事情没那么简单，因为摄影师对照片有自己的艺术追求。他带来了 $n$ 顶高度从 $1$ 到 $n$ 的尖顶帽子，每顶高度都不一样，并宣布每个小矮人都要戴上一顶。而且，在每张照片中，小矮人必须按照帽子高度从小到大的顺序站好。

于是，小矮人们开始琢磨，哪顶帽子该给哪个小矮人，才能既满足他们的愿望，又符合摄影师的要求呢？

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ $(2 \leq n \leq 500000, 0 \leq m \leq 500000)$，分别表示小矮人的数量和朋友对的数量。为了方便，我们给小矮人从 $1$ 到 $n$ 编号，其中 Gburk 是 $1$ 号，Wesołek 是 $2$ 号。

接下来的 $m$ 行描述朋友对，每行包含两个整数 $a$ 和 $b$ $(1 \leq a, b \leq n, a \neq b)$，表示编号为 $a$ 和 $b$ 的小矮人是彼此的朋友。每个小矮人的朋友数量都是偶数。

输出格式

输出的第一行，你的程序需要输出一个词：TAK 或 NIE，表示是否能成功分配帽子。如果答案是 TAK，第二行需要输出 $n$ 个整数 $h_{1}, h_{2}, \ldots, h_{n}$ $(1 \leq h_{i} \leq n)$，用单个空格分隔，其中 $h_{i}$ 表示分配给编号 $i$ 的小矮人的帽子高度。如果有多个正确答案，你的程序可以输出任意一种。

6 7
5 6
1 4
4 5
5 3
1 5
3 2
2 6

TAK
1 6 5 2 3 4

提示

附加样例

1. 该样例满足 $n=5$，所有人互为朋友，答案为 NIE；
2. 该样例满足 $n=1000$，每个小矮人有 $2$ 个朋友，答案为 TAK；
3. 该样例满足 $n=500000$，每个小矮人有 $2$ 个朋友，答案为 TAK。

详细子任务附加限制及分值如下表所示。