题目描述

题目译自 NordicOI 2022 T1 「Hipster Jazz」

一所爵士乐学校刚刚开设了一个新班级，班里有 $N$ 名学生。其中有 $M$ 对学生是朋友。每个学生都必须选择一种乐器作为他们学习的重点，要么是钢琴，要么是萨克斯。当然，所有学生都希望成为非常独特的爵士音乐家。因此，他们希望确保至少有一半的朋友选择与自己不同的乐器。

学生们发现自己很难以这种方式选择乐器，所以他们向你寻求帮助。你能为每个学生选择一种乐器，使得至少一半的朋友选择另一种乐器吗？

输入格式

第一行包含两个整数，学生人数 $N$ $(1 \le N \le 200)$ 和朋友对数 $M$ $(0 \le M \le \frac{N(N - 1)}{2})$。

接下来是 $M$ 行，每行描述一对朋友关系。每行包含两个整数 $a$ 和 $b$ $(1 \le a \neq b \le N)$，表示第 $a$ 个学生和第 $b$ 个学生是朋友。每对朋友关系只会出现一次。

输入数据保证总能找到一种有效的乐器选择方案。

输出格式

输出一个包含 $N$ 个字符的字符串。第 $i$ 个字符表示第 $i$ 个学生选择的乐器：$\texttt{P}$ 表示钢琴，$\texttt{S}$ 表示萨克斯。

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

数据范围与提示

详细子任务附加限制及分值如下表所示。