A Series of Tubes

A company has developed a way to send matter through optical fiber cables. It already owns a fiber network that reaches every state capital in the country, and it wants to move cargo over that network. The old joke that the internet is not a truck you dump things into but a series of tubes turned out to be literally useful.

The network is made of fiber branches and concentrators. Each capital holds one concentrator, and one fiber branch directly joins two concentrators. Not every pair of concentrators is joined by a branch, but the network is connected: starting from any concentrator you can reach any other concentrator by following branches and concentrators in turn.

For data traffic a branch carries messages in both directions. The new technology has a quirk. Once a branch carries matter in one direction, the fiber remembers that direction, and from then on the branch can carry matter only that way. Concentrators are not affected by this memory.

Write a program that decides whether a direction can be fixed on every branch so that cargo can still be sent from any capital to any other capital.

The input holds several test cases.

The first line of a test case has the number of capitals $N$ and the number of fiber branches $M$, separated by one space ($2 \le N \le 1000$, $1 \le M \le 50000$). The capitals are numbered 1 through $N$.

Each of the next $M$ lines has two integers $A$ and $B$ ($1 \le A, B \le N$, $A \ne B$), meaning a branch directly joins capital $A$ and capital $B$. For data traffic this branch works from $A$ to $B$ and from $B$ to $A$, but for matter transfer it works in one direction only. At most one branch joins a given pair of capitals. The network of each test case is connected.

The end of the input is a line where $N$ and $M$ are both 0. That line is not a test case.

Print one line for each test case. Print S if the network can be used as described, and N otherwise.