P10643 [NordicOI 2022] Hipster Jazz

Translated from Nordic Olympiad in Informatics 2022 [Hipster Jazz](https://noi22.kattis.com/contests/noi22/problems/hipsterjazz)。If you find that the SPJ is broken, please contact the problem porter qvq。 $\texttt{1s,1G}$。

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。

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 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。

#### 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 | Subtask ID | Score | Constraint | | :--: | :--: | :--: | | $1$ | $10$ | Every pair of students are friends | | $2$ | $15$ | $N \le 15$ | | $3$ | $25$ | There exists a solution where every pair of friends choose different instruments | | $4$ | $50$ | No additional constraints | Translated by ChatGPT 5