爵士乐学校新开了一个班，共有 $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

输出 1

PSP

输入 2

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

输出 2

SPPSP

输入 3

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

输出 3

PPPSSS