#2426. 「POI2010」工会 Guilds

内存限制:64 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: luyanaa

题目描述

译自 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 个点不建立办事处。

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

样例

样例输入

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

数据范围与提示

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

Translated By diamond_duke