URI Online Judge | 1203

St. Petersburg Bridges

By Renato Parente Brazil

Timelimit: 1

Everyone knows the famous problem of the bridges of Königsberg, the Prussian city that was the famous problem solved by Euler still in the eighteenth century. Few know, however, problem of the bridges of St. Petersburg. The city of St. Petersburg is located on the banks of Neva River, and is crossed by dozens of bridges connecting the riverbanks to hundreds of small islands that the river has. The residents of the city, knowing famous problem of bridges Königsberg, created their own problem. Locals know that there are K bridges in the city, R that are distinct regions in the city and that each bridge connects exactly two distinct regions of the city. Residents want to know if, to their city, you can choose some of these regions such the number of bridges which focuses on them all is equal to K. Note that, if two of these regions chosen have a bridge between them, this bridge will be counted twice.


The input consists of various instances and ends with the end of file (EOF). The first line of each test case contains two numbers, R (2 ≤ R ≤ 100) and K (1 ≤ KR * (R-1) / 2), the number of regions, and bridges of the city, respectively. For purposes of simplification, the regions are numbered 1 to R, inclusive. The following are K lines, each containing two numbers A and B, indicating that there is a bridge linking the A and B regions of the city.


For each test case print a line only with "S" (quotes just for show) if it is possible choose the regions in the manner described above, or "N" (idem), if not possible.

Sample Input Sample Output

2 1
1 2
3 3
1 2
1 3
3 2