题目描述

题目译自 XV OI Olimpiada Informatyczna – I etap Cło

国王 Bajtazar 决定整顿拜托西亚商人的关税缴纳事务。拜托西亚由 $n$ 个城市组成，通过 $m$ 条双向道路连接。每条道路连接两个不同城市，且任意两城市间至多有一条道路。道路可能穿越隧道或高架桥。

此前，每城市对进出商人都收取关税。商人对此不满，正式抗议重复收费。Bajtazar 决定限制城市权限，颁布新法令：每城市仅可对一条通往它的道路（不论旅行方向）收取关税；每条道路的商人不得被其连接的两个城市同时课税。你需决定每城市从哪条道路收税，国王将此任务委托给你。

编写程序：

• 从标准输入读取拜托西亚道路网络描述。
• 为每城市指定其收取关税的道路，或判定法令无法实施。
• 将结果输出到标准输出。

输入格式

第一行包含两个整数 $n, m$ $(1 \leq n \leq 100000, 1 \leq m \leq 200000)$，分别表示城市数和道路数。城市从 $1$ 到 $n$ 编号。接下来的 $m$ 行描述道路，每行包含两个整数 $a_i, b_i$ $(1 \leq a_i < b_i \leq n)$，表示城市 $a_i$ 和 $b_i$ 通过一条道路直接连接。

输出格式

若无法按法令收取关税，仅输出一行 NIE。否则，第一行输出 TAK，接下来的 $n$ 行描述每城市收取关税的道路：第 $i+1$ 行包含一个整数，表示与城市 $i$ 连接的城市编号，其对应道路由城市 $i$ 收税。若存在多种方案，输出任意一种。

4 5
1 2
2 3
1 3
3 4
1 4

TAK
3
3
4
1

图中箭头指示收取关税的城市。注意，沿连接城市 $1$ 和 $2$ 的道路旅行的商人完全免税。

4 3
1 3
3 4
2 3

NIE