Problem Background

Translated from the Nordic Olympiad in Informatics 2022 Hipster Jazz. If there are issues with the SPJ, please contact the problem搬运人 qvq.

$\texttt{1s, 1G}$.

Problem Description

In a jazz school, a new class has been formed. This class consists of $N$ students, with $M$ pairs of friendships among them. Each student must choose a primary instrument: piano or saxophone. Naturally, all students want to be creative jazz musicians, so they want to ensure that at least half of their friends have a different primary instrument than they do.

The students find choosing an instrument to be a difficult task. Therefore, they have sought your help to select a primary instrument for each student, satisfying the above condition.

The data guarantees that at least one solution exists.

Input Format

The first line contains two positive integers $N$ and $M$, as described in the problem statement.

The following $M$ lines each contain two numbers $a$ and $b$, indicating that $a$ and $b$ are friends.

It is guaranteed that no pair of friends will be listed twice. It is also guaranteed that at least one solution exists.

Output Format

Output a string of $N$ characters. The $i$-th character should be P if the $i$-th student chooses piano, and S if the $i$-th student chooses saxophone.

Sample Input and Output

Sample Input #1

3 3
1 2
1 3
2 3

Sample Output #1

PSP

Sample Input #2

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

Sample Output #2

SPPSP

Sample Input #3

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

Sample Output #3

PPPSSS

Notes

Data Range

• $1 \le N \le 200$;
• $0 \le M \le \frac{N(N-1)}{2}$;
• No pair of friends will be listed twice;
• At least one solution exists.

Subtasks

见题面 Input 部分

见题面 Output 部分