题目描述
题目译自 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$ 个学生选择的乐器：P 表示钢琴，S 表示萨克斯。

---

样例 1

输入：

3 3
1 2
1 3
2 3

输出：

PSP

解释：学生1选钢琴(P)，学生2选萨克斯(S)，学生3选钢琴(P)。每个学生都有2个朋友，其中至少1个（一半）选择了不同的乐器。

---

样例 2

输入：

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

输出：

SPPSP

---

样例 3

输入：

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

输出：

PPPSSS

---

数据范围与提示

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

子任务	分值	附加限制
1	10	每对学生都是朋友
2	15	$N \le 15$
3	25	存在一个方案，没有两个朋友演奏相同的乐器
4	50	无附加限制