1374. Motorways

输入格式

In the first line of the standard input there are two integers: the number of towns n and the number of the planned motorways k, 1 <= n,k <= 20000. In the following lines there are pairs of towns which are to be connected by motorways. In the (i+1)-st line there are two integers pi, qi separated by a single space: the numbers of the towns that the i-th motorway is to connect, 1 <= pi < qi <= n. Pairs of towns are not repeated in the input data.

输出格式

Your program should write to the standard output an arrangement plan of the motorways or a single word NIE (“no” in Polish), if it is not possible to construct all the motorways according to the given rules. If the construction of the motorways is possible then your program should write k lines to the standard output. In the i-th line there should be one capital letter, respectively: N - if the motorway connecting the towns pi and qi should be constructed to the north of the railway line, or S - if to the south of the railway line. If there exist many possible solutions, your program should write only one of them (arbitrary).

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

N
N
S
S
S
N
N