P10643 [NordicOI 2022] 嬉皮爵士 Hipster Jazz

译自 Nordic Olympiad in Informatics 2022 [Hipster Jazz](https://noi22.kattis.com/contests/noi22/problems/hipsterjazz)。如果发现 SPJ 锅了请联系搬题人 qvq。 $\texttt{1s,1G}$。

爵士学校里，新班级诞生了。这个班级里有 $N$ 名学生，其中有 $M$ 对朋友关系。每个学生要选择一种主修乐器：钢琴，或者萨克斯。当然，所有的学生都希望成为有创意的爵士音乐家，所以他们想要保证，至少有一半朋友主修的乐器和自己主修的乐器不一样。 学生们发现，选择乐器是一件很困难的事情。于是他们找来了你，希望你能够为每个同学选择一个主修乐器，满足上述条件。 数据保证至少存在一种方案。

第一行，两个正整数 $N,M$，含义见题面。 接下来 $M$ 行，每行两个数 $a,b$，表示 $a,b$ 是朋友。 保证同一对朋友不会被列出两次。保证至少存在一种方案。

输出一行含 $N$ 个字符的字符串。第 $i$ 个字符为 `P`，代表第 $i$ 名学生选择钢琴；第 $i$ 个字符为 `S`，代表第 $i$ 名学生选择萨克斯。

#### 数据范围 - $1\le N\le 200$； - $0\le M\le \dfrac{N(N-1)}{2}$； - 同一对朋友不会被列出两次； - 至少存在一种方案。 #### 子任务 | 子任务编号 | 得分 | 限制 | | :--: | :--: | :--: | | $1$ | $10$ | 每对学生都是朋友 | | $2$ | $15$ | $N\le 15$ | | $3$ | $25$ | 存在一种方案，其中任意一对朋友主修的乐器都不同 | | $4$ | $50$ | 无额外限制 |