Seven Kingdoms

Jon Dayne rules a huge country called the Seven Kingdoms. He wants to give some of its cities to his two sisters, Arya and Sansa, and rule whatever is left himself. If no city is left, he leaves for the Wall, the colossal fortification along the northern border, to be the Lord Commander.

Arya is the Lady of Winterfell and Sansa is the Lady of King's Landing. The cities of the Seven Kingdoms, Winterfell and King's Landing included, are joined by a network of roads. Some cities may be cut off from all the others, either because they sit on an island or because they are at war with their neighbours. There is no road between Winterfell and King's Landing, and no city has a road to both of them.

Jon wants to split every city into three groups.

• The group he gives to Arya, which must contain Winterfell.
• The group he gives to Sansa, which must contain King's Landing.
• The group he keeps, which may be empty.

Any two cities in the same group must be joined by a direct road. Decide whether such a split exists, and report it if it does.

The first line contains the number of cities $n$ and the number of roads $m$ ($2 \le n \le 2000$).

Each of the next $m$ lines contains two different integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$) describing one road, which joins city $x_i$ and city $y_i$.

Winterfell is city 1 and King's Landing is city 2. No road joins city 1 and city 2, and no city has a road to both of them.

If no split satisfies the conditions, print impossible.

Otherwise print one line of $n$ characters. The $i$-th character is A if city $i$ goes to Arya, S if it goes to Sansa, and J if Jon keeps it. City 1 is always A and city 2 is always S.

If several splits are valid, print the lexicographically smallest such string. The character order is A, J, S.