Byteasar 国王面临一个严峻的问题。两个相互竞争的贸易组织——裁缝公会（The Tailors Guild）和下水道公会（The Sewers Guild）——同时请求在王国的每个城镇开设办事处。

Byteotia 共有 $n$ 个城镇，其中一些城镇由双向道路连接。每个公会都要求每个城镇必须满足以下条件之一：

• 拥有该公会的办事处，或者
• 直接连接到另一个拥有该公会办事处的城镇。

然而，国王怀疑其中有猫腻。他担心如果有一个城镇同时设有这两个公会的办事处，可能会导致服装卡特尔的形成。因此，他请求你的帮助。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 200\,000$, $0 \le m \le 500\,000$)，分别表示 Byteotia 的城镇数量和道路数量。城镇编号从 $1$ 到 $n$。接下来的 $m$ 行描述道路：第 $i+1$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$)，表示第 $i$ 条道路连接城镇 $a_i$ 和 $b_i$。每对城镇之间最多只有一条直接相连的道路。道路不会交叉（只在城镇处相交），但可能通过隧道或立交桥。

输出格式

如果可以按照这些规则放置办事处，程序应在第一行输出 TAK（波兰语中的“是”），否则输出 NIE（波兰语中的“否”）。如果答案为 TAK，则接下来的 $n$ 行应给出一个办事处放置的示例。第 $i+1$ 行应包含：

• 字母 K，如果城镇 $i$ 应设有裁缝公会的办事处；
• 字母 S，如果城镇 $i$ 应设有下水道公会的办事处；
• 字母 N，如果城镇 $i$ 不应设有任何办事处。

样例

输入 1

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

输出 1

TAK
K
S
K
S
K
K
N

图中圆圈标记的城镇应开设裁缝公会办事处，菱形标记的城镇应开设下水道公会办事处。