일곱 왕국

존 데인은 일곱 왕국이라는 거대한 나라를 다스린다. 여동생 아리아와 산사에게 도시를 얼마간 나누어 주고, 남은 도시는 자신이 다스린다. 남는 도시가 하나도 없으면 북쪽 국경을 따라 세운 거대한 성벽인 장벽으로 떠나 총사령관이 된다.

아리아는 윈터펠의 영주이고 산사는 킹스랜딩의 영주다. 윈터펠과 킹스랜딩을 포함한 일곱 왕국의 도시는 도로망으로 이어져 있다. 섬에 있거나 이웃 도시와 전쟁 중이라 다른 도시와 전혀 이어지지 않은 도시도 있다. 윈터펠과 킹스랜딩을 직접 잇는 도로는 없고, 두 도시 모두와 도로로 이어진 도시도 없다.

존은 모든 도시를 세 묶음으로 나누려 한다.

• 아리아가 받는 묶음. 윈터펠을 포함해야 한다.
• 산사가 받는 묶음. 킹스랜딩을 포함해야 한다.
• 존이 남기는 묶음. 비어 있어도 된다.

같은 묶음에 속한 두 도시는 도로로 직접 이어져 있어야 한다. 이런 분할이 가능한지 판단하고, 가능하면 분할을 알려 주자.

첫 줄에 도시 수 $n$과 도로 수 $m$이 주어진다 ($2 \le n \le 2000$).

다음 $m$개 줄에는 도로 하나를 나타내는 서로 다른 두 정수 $x_i$와 $y_i$가 주어진다 ($1 \le x_i, y_i \le n$). 이 도로는 도시 $x_i$와 도시 $y_i$를 잇는다.

윈터펠은 1번 도시, 킹스랜딩은 2번 도시다. 1번과 2번을 직접 잇는 도로는 없고, 두 도시 모두와 이어진 도시도 없다.

조건을 만족하는 분할이 없으면 impossible을 출력한다.

분할이 있으면 $n$개 문자로 이루어진 한 줄을 출력한다. $i$번째 문자는 $i$번 도시를 아리아가 받으면 A, 산사가 받으면 S, 존이 남기면 J다. 1번 도시는 항상 A이고 2번 도시는 항상 S다.

가능한 분할이 여러 개면 사전순으로 가장 앞서는 문자열을 출력한다. 문자 순서는 A, J, S다.