新年聚会上共有 $n$ 个小矮人。小矮人们希望留下美好的回忆，于是邀请了一位摄影师为每个小矮人拍摄一张与他朋友们的合影。除了 Gburek 和 Wesołek（他们对此无所谓，尽管原因各不相同）之外，每个小矮人都希望在自己的照片中站在正中间（幸运的是，每个小矮人都有偶数个朋友）。

然而，这并不简单，因为摄影师对照片也有自己的艺术构想。他带来了 $n$ 顶高度各不相同的尖顶帽，高度从 $1$ 到 $n$ 不等，并宣布每个小矮人必须戴上一顶帽子，此外，在每张照片中，小矮人们必须按照帽子高度升序排列。

小矮人们开始思考，应该如何分配帽子，才能同时满足他们的愿望和摄影师的构想。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 500\,000$, $0 \le m \le 500\,000$)，分别表示小矮人的数量和朋友对的数量。为简化起见，小矮人编号从 $1$ 到 $n$，其中 Gburek 的编号为 $1$，Wesołek 的编号为 $2$。

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

输出格式

第一行输出一个单词 TAK 或 NIE，表示是否可以为小矮人分配帽子。如果答案是肯定的，则在第二行输出一个包含 $n$ 个整数的序列 $h_1, h_2, \dots, h_n$ ($1 \le h_i \le n$)，数字之间用空格隔开；其中 $h_i$ 表示分配给编号为 $i$ 的小矮人的帽子高度。如果存在多种合法的分配方案，输出其中任意一种即可。

样例

输入 1

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

输出 1

TAK
1 6 5 2 3 4

子任务

测试集分为以下子任务。每个子任务的测试用例由一组或多组独立的测试组组成。