题目描述

爵士学校里，新班级诞生了。这个班级里有 $N$ 名学生，其中有 $M$ 对朋友关系。

每个学生要选择一种主修乐器：

• 钢琴，用字符 P 表示；
• 萨克斯，用字符 S 表示。

当然，所有学生都希望成为有创意的爵士音乐家，所以他们想要保证：

对于每一名学生，至少有一半朋友选择的乐器和自己不同。

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

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

输入格式

第一行输入两个整数 $N,M$，分别表示学生数量和朋友关系数量。

接下来 $M$ 行，每行两个整数 $a,b$，表示第 $a$ 名学生和第 $b$ 名学生是朋友。

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

输出格式

输出一行长度为 $N$ 的字符串。

第 $i$ 个字符表示第 $i$ 名学生选择的乐器：

• P 表示钢琴；
• S 表示萨克斯。

若有多组合法答案，输出任意一组即可。

数据范围

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

子任务