题目描述

译自 POI 2010 Stage 1.「Guilds」

给定一个 $n$ 个城市 $m$ 条道路的某国地图，某国有两个工会。要求每个城市要么：

• 有某个工会的办事处。
• 与另外一个有办事处的城市有道路直接相连。

但是任何一个城市不能有超过一个公会的办事处，求是否能够做到，若可以，请构造一种方案。

输入格式

第一行两个整数 $n$ 和 $m$ ， $n$ 代表城市数， $m$ 代表道路数。
接下来 $m$ 行每行两个整数 $a_i$ 和 $b_i$ ，表示 $a_i$ 和 $b_i$ 有边相接，保证不会出现重边。

输出格式

第一行一个字符串，如果能够做到则输出 TAK ，否则输出 NIE 。
若能做到，接下来 $n$ 行，每行一个字母，表示你的方案，第 $i+1$ 行的含义如下：

• K 表示第 $i$ 个点建立第一家工会的办事处；
• S 表示第 $i$ 个点建立第二家工会的办事处；
• N 表示第 $i$ 个点不建立办事处。

若有多解，输出任意一种均可。

样例

input

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

output

TAK
K
S
K
S
K
K
N

数据范围与提示

对于 $100\%$ 的数据， $n \le 2 \times 10^5 , m \le 5 \times 10^5$ 。

Translated By diamond_duke