You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

国王 Byteasar 面临一个严峻的问题。

两个相互竞争的贸易组织——裁缝行会（The Tailors Guild）和缝纫行会（The Sewers Guild）同时要求获得许可，在王国每个城镇设立办事处。

Byteotia 有 $n$ 个城镇。

其中一些城镇通过双向道路连接。

每个行会都要求：

• 每个城镇必须设有本行会的办事处

• 或者该城镇必须直接连接到一个设有本行会办事处的城镇。

然而，国王怀疑其中有诈。他担心如果存在某个城镇同时设有两个行会的办事处，可能会导致服装垄断。

因此，他请求你的帮助。

输入格式

标准输入的第一行包含两个整数 $n$ ($n \leq 200000$) 和 $m$ ($m \leq 500000$)，分别表示 Byteotia 的城镇数量和道路数量。

城镇编号为 $1$ 到 $n$。

接下来 $m$ 行描述道路：输入的第 $i+1$ 行描述第 $i$ 条道路；

输出格式

你的程序应在标准输出的第一行输出一个单词：

• TAK（波兰语中的"是"）——表示可以按照规则在城镇中设置办事处，或者

• NIE（波兰语中的"否"）——表示无法满足条件。

如果答案是 TAK，则接下来的 $n$ 行应给出一种可行的办事处设置方案。因此第 $i+1$ 行应包含：

• 字母 K —— 表示城镇 $i$ 应设有裁缝行会（The Tailors Guild）的办事处，或

• 字母 S —— 表示城镇 $i$ 应设有缝纫行会（The Sewers Guild）的办事处，或

• 字母 N —— 表示城镇 $i$ 不应设有任何行会的办事处。

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

TAK
K
S
K
S
K
K
N

提示

题目spj贡献者@mengbierr

翻译：DeepSeek-R1