Problem : 95 - 議會設置

Special Judge

Problem Statistics

Solved Member: 37　　Submission: 88　　User Tried: 37

Statement:

兔子國統治了銀河系的 N 個星球，由編號1到N表示。
星球之間由 M 條雙向的道路相連，每條路連接恰好2個不同的星球。
首先，他必須透過議會以及政府對每個星球做約束。

兔王希望，每個星球與政府以及議會都不可以隔太遠，他希望可以滿足以下的條件：
1.每個星球可以設立一個議會，或者一個政府，或者可以都不設立，但是不可以兩者都設立。
2.每一個星球與政府以及議會都至少要相鄰，或者建立在該星球上。

由於兔王現在很忙，他決定請你幫他規劃出一個可行的方案。

Input:Output:

第1行有兩個正整數N,M (N ≤ 200000; M ≤ 500000)。
接下來 M 行，每行有 2 個正整數A,B，代表A星球與B星球是相連的。

若存在一種滿足兔王要求的方案，第一行請輸出"TAK"。
接著 N 行，第 i+1 行可以輸出三種英文字母 K(建立議會)；S(建立政府)；N(什麼都不設置)，代表第 i 個星球的建設方案。

如果沒有解，第一行輸出"NIE"即可。

Sample Input:Sample Output:

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

HINT:

範例輸出的圖形，圓圈代表議會(K)，菱形代表政府(S)，若都沒有代表不建設(N)。

Source:

POI 17 Stage 1

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1-ocen	1000ms	65536kb
1-1	1000ms	65536kb	8
1-2	1000ms	65536kb
2-ocen	1000ms	65536kb
2-1	1000ms	65536kb	8
2-2	1000ms	65536kb
3-ocen	1000ms	65536kb
3-1	1000ms	65536kb	8
3-2	1000ms	65536kb
4-ocen	5000ms	65536kb
4-1	1000ms	65536kb	8
4-2	1000ms	65536kb
5-1	4000ms	65536kb	8
5-2	4000ms	65536kb
6	4000ms	65536kb	8
7-1	2000ms	65536kb	8
7-2	1000ms	65536kb
8-1	2000ms	65536kb	8
8-2	2000ms	65536kb
9	2000ms	65536kb	9
10-1	2000ms	65536kb	9
10-2	4000ms	65536kb
11-1	2000ms	65536kb	9
11-2	2000ms	65536kb
12-1	3000ms	65536kb	9
12-2	3000ms	65536kb