#P3496. [POI 2010] GIL-Guilds

    ID: 4337 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>搜索贪心2010POI(波兰)Special Judge广度优先搜索 BFS

[POI 2010] GIL-Guilds

题目描述

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

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

Byteotia 有 nn 个城镇。

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

每个行会都要求:

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

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

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

因此,他请求你的帮助。

输入格式

标准输入的第一行包含两个整数 nn (n200000n \leq 200000) 和 mm (m500000m \leq 500000),分别表示 Byteotia 的城镇数量和道路数量。

城镇编号为 11nn

接下来 mm 行描述道路:输入的第 i+1i+1 行描述第 ii 条道路;

输出格式

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

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

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

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

  • 字母 K —— 表示城镇 ii 应设有裁缝行会(The Tailors Guild)的办事处,或

  • 字母 S —— 表示城镇 ii 应设有缝纫行会(The Sewers Guild)的办事处,或

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

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