题目背景

译自 Nordic Olympiad in Informatics 2022 Hipster Jazz。如果发现 SPJ 锅了请联系搬题人 qvq。

$\texttt{1s,1G}$。

题目描述

爵士学校里，新班级诞生了。这个班级里有 $N$ 名学生，其中有 $M$ 对朋友关系。每个学生要选择一种主修乐器：钢琴，或者萨克斯。当然，所有的学生都希望成为有创意的爵士音乐家，所以他们想要保证，至少有一半朋友主修的乐器和自己主修的乐器不一样。

学生们发现，选择乐器是一件很困难的事情。于是他们找来了你，希望你能够为每个同学选择一个主修乐器，满足上述条件。

数据保证至少存在一种方案。

输入格式

第一行，两个正整数 $N,M$，含义见题面。

接下来 $M$ 行，每行两个数 $a,b$，表示 $a,b$ 是朋友。

保证同一对朋友不会被列出两次。保证至少存在一种方案。

输出格式

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

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

提示

数据范围

• $1\le N\le 200$；
• $0\le M\le \dfrac{N(N-1)}{2}$；
• 同一对朋友不会被列出两次；
• 至少存在一种方案。

子任务