Byteasar 国王在 Byteotian 商人的压力下屈服了，因此决定解决他们缴纳通行费的问题。Byteotia 由 $n$ 个城镇和 $m$ 条双向道路连接而成。每条道路直接连接两个不同的城镇，且任意两个城镇之间最多只有一条直接道路。注意，道路可能通过隧道或高架桥。

到目前为止，Byteotia 的每个城镇都会对所有进入或离开该城镇的人征税。商人们对这种重复征税的情况感到不满，并提出了抗议。Byteasar 国王裁定，城镇的特权现在受到限制。根据新的皇家法令，每个城镇只能对通过连接该城镇的某一条特定道路的商人征收通行费，无论他们行进的方向如何。此外，对于每一条道路，通过该道路的商人不能被要求向该道路连接的两个城镇同时缴纳通行费。现在需要确定每个城镇应该从哪条道路收取通行费。国王已将此问题委托给你解决。

编写一个程序：

• 从标准输入读取 Byteotia 道路系统的描述，
• 为每个城镇确定它应该对哪条道路征收通行费，或者声明这是不可能的，
• 将结果写入标准输出。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 100\,000$, $1 \le m \le 200\,000$)，分别表示 Byteotia 的城镇数量和道路数量。城镇编号从 $1$ 到 $n$。接下来的 $m$ 行描述了道路。第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i < b_i \le n$)，表示城镇 $a_i$ 和 $b_i$ 之间由一条道路直接相连。

输出格式

如果按照皇家法令征收通行费是不可能的，你的程序应该在标准输出的第一行（也是唯一一行）输出单词 NIE（波兰语中的“不”）。否则，第一行应输出单词 TAK（波兰语中的“是”），接下来的 $n$ 行应说明每个城市从哪条道路收取通行费。第 $i+1$ 行应说明城镇 $i$ 对哪条道路征收通行费。由于城镇 $i$ 显然是该道路的一个端点，因此只需说明另一个端点是什么。因此，如果城镇 $i$ 对连接它与城镇 $j$ 的道路征收通行费，则第 $i+1$ 行应包含数字 $j$。如果存在多个解，输出其中任意一个即可。

样例

输入 1

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

输出 1

TAK
3
3
4
1

图中的箭头指向从使用该道路的商人处收取通行费的城镇。请注意，沿连接城镇 1 和 2 的道路行驶的商人根本不需要缴纳通行费。

输入 2

4 3
1 3
3 4
2 3

输出 2

NIE