P12913 [POI 2020/2021 R2] 小矮人摄影 / Zdjęcia krasnali

翻译来自于 [LibreOJ](https://loj.ac/p/4831)。

**题目译自 [XXVIII Olimpiada Informatyczna – II etap](https://sio2.mimuw.edu.pl/c/oi28-2/dashboard/) [Zdjęcia krasnali](https://szkopul.edu.pl/problemset/problem/GfCNwxdYubiS1Nlnb_h7VkJW/statement/)** 在新年派对上，有 $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$ 的小矮人的帽子高度。如果有多个正确答案，你的程序可以输出任意一种。

**附加样例** 1. 该样例满足 $n=5$，所有人互为朋友，答案为 `NIE`； 2. 该样例满足 $n=1000$，每个小矮人有 $2$ 个朋友，答案为 `TAK`； 3. 该样例满足 $n=500000$，每个小矮人有 $2$ 个朋友，答案为 `TAK`。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n \leq 10$ | $15$ | | $2$ | $m \leq 20$ | $20$ | | $3$ | $n, m \leq 1000$ | $25$ | | $4$ | 无附加限制 | $40$ |