Problem A
Hipster Jazz

A new class has just started at jazz school, consisting of $N$ students. Among them, $M$ pairs of students are friends. Each student has to pick an instrument to focus on during their studies, either piano or saxophone. Of course, all the students want to be very original jazz musicians. Therefore, they want to make sure that at least half of their friends choose a different instrument than what they chose.

It turned out to be hard for the students to choose instruments in this manner by themselves, so they turned to you for some help. Can you select an instrument for each child, such that at least half of their friends play the other instrument?

Input

The first line contains the number of students $N$ ($1\le N\le 200$) and pairs of friends $M$ ($0\le M\le \frac{N(N-1)}{2}$).

This is followed by $M$ lines, one for each friendship. A friendship is described by two integers $a$ and $b$ ($1\le a\ne b\le N$), denoting that the $a$’th and $b$’th students are friends. No friendship will be listed twice.

The input will always be chosen in such a way that a valid selection of instruments for the students exists.

Output

Output a single string with $N$ characters. The $i$’th character should denote the instrument of the $i$’th student: either P if they should play the piano, or S if they should play the saxophone.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group.

3 3
1 2
1 3
2 3

PSP

5 6
1 2
1 3
1 5
2 4
3 5
4 5

SPPSP

6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6

PPPSSS