TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P2833
  • 問題
  • P2833区间
    制限 : 時間制限 : 10000 MS   メモリ制限 : 131072 KB  SPJ
    審判説明 : 1s,128MB,SPJ
    問題説明

    定义两个区间冲突当且仅当它们的交区间的长度大于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$