Jazz Instrument Selection

There is a new class in the Jazz School with (N) students and (M) pairs of friendship among them. Each student must choose a major instrument: (\text{Piano}) or (\text{Sax}). The students want to ensure that at least half of their friends play a different instrument than themselves. In other words, for each student (u) with degree (d_u), if the number of friends playing a different instrument is (k), then the condition (k \geq \lceil d_u/2 \rceil) must hold. It is guaranteed that there is at least one valid assignment.

inputFormat

The first line contains two integers (N) and (M). Each of the following (M) lines contains two integers (u) and (v) indicating that student (u) and student (v) are friends. The students are numbered from (1) to (N).

outputFormat

Output a sequence of (N) words separated by a space. Each word must be either (Piano) or (Sax), representing the chosen instrument for the corresponding student.

sample

3 2
1 2
2 3

Piano Sax Piano