Background

Translated from Nordic Olympiad in Informatics 2022 Hipster Jazz。If you find that the SPJ is broken, please contact the problem porter qvq。

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

Problem Description

In the jazz school, a new class has been formed。There are $N$ students in this class, with $M$ pairs of friendships。Each student has to choose one main instrument: piano, or saxophone。Of course, all students want to become creative jazz musicians, so they want to ensure that at least half of their friends choose a different instrument from their own。

The students realized that choosing instruments is difficult。So they came to you, hoping that you can choose a main instrument for each student and satisfy the condition above。

The testdata guarantees that at least one solution exists。

Input Format

The first line contains two positive integers $N, M$, with meanings as described in the statement。

The next $M$ lines each contain two numbers $a, b$, meaning that $a$ and $b$ are friends。

It is guaranteed that the same pair of friends will not be listed twice。It is guaranteed that at least one solution exists。

Output Format

Output a single line containing a string of $N$ characters。The $i$-th character is P, meaning the $i$-th student chooses piano; the $i$-th character is S, meaning the $i$-th student chooses saxophone。

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

Hint

Constraints

• $1 \le N \le 200$；
• $0 \le M \le \dfrac{N(N-1)}{2}$；
• The same pair of friends will not be listed twice；
• At least one solution exists。

Subtasks

Translated by ChatGPT 5