Motorways

Byteotia lies on a peninsula. Ever since the reign of King Byteol, railways have been the main means of transport there. King Byteol had a super-speed railway line built that connects the western and eastern coasts of the peninsula. It runs through every town of Byteotia and so fixes their numbering: the first town on the line is town $1$ and the last is town $n$. Town $1$ lies on the western coast and town $n$ on the eastern coast.

Fig. 1. The Byteotian railway line.

Thanks to minister Byterowicz the economy has grown quickly, and the transport network must be modernised. King Byteol has ordered $k$ motorways to be built. Each motorway directly joins two chosen towns. Because every motorway is built by a different agency with its own vignette, no motorway may cross another motorway or the railway line. The only way to achieve this is to build each motorway either to the north or to the south of the railway line, drawn as an arc between its two towns.

Fig. 2. A sample arrangement of the motorways joining towns 1-2, 1-3, 2-4, 5-7, 4-8, 7-8, 6-8 (arcs are dotted, the railway line is solid).

Two motorways placed on the same side of the railway cross exactly when their town intervals interleave: exactly one endpoint of one motorway lies strictly between the two endpoints of the other. Motorways that share a town, that are nested one inside the other, or that are completely separate never cross and may share a side. Motorways on opposite sides never cross.

King Byteol has already fixed which pairs of towns are to be joined. Decide, for every motorway, whether it goes to the north or to the south of the railway line so that no two motorways cross, or report that no such placement exists.

The first line contains two integers $n$ and $k$ ($1 \le n, k \le 20000$): the number of towns and the number of planned motorways.

Each of the next $k$ lines contains two integers $p_i$ and $q_i$ ($1 \le p_i < q_i \le n$): the towns joined by the $i$-th motorway. No pair of towns is repeated.

If no valid placement exists, print a single line containing IMPOSSIBLE.

Otherwise print $k$ lines. The $i$-th line contains one uppercase letter for the $i$-th motorway (in input order): N if that motorway must be built to the north of the railway line, or S if to the south.

Several placements may be valid. Among all valid placements, print the lexicographically smallest one, reading the $k$ letters from top to bottom as a single string and treating N as smaller than S.