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

输入输出样例 #1

输入 #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

说明/提示

题目spj贡献者@mengbierr

翻译：DeepSeek-R1