P3496 [POI 2010] GIL-Guilds

国王 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$ 不应设有任何行会的办事处。

题目spj贡献者@mengbierr 翻译：DeepSeek-R1