Byteotia 位于一个半岛上。从 Bitol 国王时代起，铁路就是 Byteotia 的主要交通工具。Bitol 国王修建了一条超高速铁路线。这条线路连接了半岛的东海岸和西海岸，贯穿了 Byteotia 的所有城镇，从而确定了它们的编号：线上的第一个城镇编号为 $1$，最后一个为 $n$。$1$ 号城镇位于西海岸，$n$ 号城镇位于东海岸。

图 1. Byteotia 铁路线

最近，得益于 Byterowicz 部长，Byteotia 的经济发展非常迅速，现有的交通网络需要快速现代化。Byteol 国王下令修建许多高速公路（在下一个 23 年计划的框架内）。每条高速公路都将直接连接 Byteotia 的两个选定城镇。由于每条高速公路都将由不同的政府机构建造，且每条高速公路上都需要使用不同的通行证，因此决定高速公路之间以及高速公路与铁路线之间不得交叉。因此，唯一的解决方案是将每条高速公路修建在铁路线的北侧或南侧。图 2 展示了一个高速公路布置的示例（虚线弧表示高速公路，实线表示铁路线）。

图 2. 连接城镇的高速公路布置示例：1-2, 1-3, 2-4, 5-7, 4-8, 7-8, 6-8

Byteol 国王陛下已经决定了哪些城镇对将由高速公路直接连接。你的任务是确定哪些高速公路应位于铁路线北侧，哪些应位于南侧。请记住，高速公路之间以及高速公路与铁路线之间不得交叉。

任务

编写一个程序，完成以下工作：

• 从标准输入读取计划修建的高速公路信息；
• 确定高速公路的位置（或指出无法按照给定规则修建）；
• 将结果写入标准输出。

输入格式

标准输入的第一行包含两个整数：城镇数量 $n$ 和计划修建的高速公路数量 $k$，$1 \le n,k \le 20\,000$。接下来的行中包含将由高速公路连接的城镇对。第 $(i+1)$ 行包含两个由空格分隔的整数 $p_i, q_i$，表示第 $i$ 条高速公路连接的城镇编号，$1 \le p_i < q_i \le n$。输入数据中不会重复出现城镇对。

输出格式

如果无法按照给定规则修建所有高速公路，你的程序应向标准输出写入一个单词 NIE（波兰语中的“不”）。如果可以修建，你的程序应向标准输出写入 $k$ 行。第 $i$ 行应包含一个大写字母：如果连接城镇 $p_i$ 和 $q_i$ 的高速公路应修建在铁路线北侧，则输出 N；如果应修建在南侧，则输出 S。如果存在多种可能的解决方案，你的程序只需输出其中任意一个即可。

样例

输入 1

8 7
1 2
1 3
2 4
5 7
4 8
7 8
6 8

输出 1

N
N
S
S
S
N
N