P2833区间 | ||
|
问题描述
定义两个区间冲突当且仅当它们的交区间的长度大于0且分别小于两个区间的长度。也就是说区间的包含、相接、相离关系都不算冲突。
给定m个区间,请将其分为两个集合,使得每个集合内的区间不冲突。
输入格式
第一行n m表示区间的范围以及区间的个数
接下来m行每行两个整数l,r描述一个区间[l,r]
输出格式
如果无解则输出“NIE”
如果有解,输出m行,每行为N或S,相同字母对应的区间分在同一集合。如果有多解,请输出任意一组即可
样例输入
8 7
1 2
1 3
2 4
5 7
4 8
7 8
6 8
样例输出
N
N
S
S
S
N
N
答案可能不唯一
提示
30%:$1\leq n,m\leq 2\times 10^3$
65%:$1\leq n,m\leq 2\times 10^4$
100%:$1\leq n,m\leq 2\times 10^5$,$1\leq l\leq r\leq m$