Problem D
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 \neq 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.
Group |
Points |
Constraints |
$1$ |
$10$ |
Every pair of students are friends |
$2$ |
$15$ |
$N \le 15$ |
$3$ |
$25$ |
A solution exists where no two friends play the same instrument |
$4$ |
$50$ |
No additional constraints |
Sample Input 1 | Sample Output 1 |
---|---|
3 3 1 2 1 3 2 3 |
PSP |
Sample Input 2 | Sample Output 2 |
---|---|
5 6 1 2 1 3 1 5 2 4 3 5 4 5 |
SPPSP |
Sample Input 3 | Sample Output 3 |
---|---|
6 9 1 4 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6 |
PPPSSS |