고속도로

바이토티아(Byteotia)는 반도에 자리 잡고 있다. 바이톨(Byteol) 왕의 시대부터 철도는 이 나라의 기본 교통수단이었다. 바이톨 왕은 반도의 서해안과 동해안을 잇는 초고속 철도 노선을 건설했다. 이 노선은 바이토티아의 모든 도시를 지나며, 그 순서대로 도시의 번호가 정해진다. 노선의 첫 번째 도시가 $1$번, 마지막 도시가 $n$번이다. $1$번 도시는 서해안에, $n$번 도시는 동해안에 있다.

그림 1. 바이토티아 철도 노선.

바이테로비치(Byterowicz) 장관 덕분에 경제가 빠르게 성장하면서 교통망을 현대화해야 하게 되었다. 바이톨 왕은 $k$개의 고속도로 건설을 명령했다. 각 고속도로는 선택된 두 도시를 직접 잇는다. 고속도로마다 서로 다른 기관이 건설하고 각기 다른 통행권이 필요하므로, 어떤 고속도로도 다른 고속도로나 철도 노선과 교차해서는 안 된다. 이를 만족시키는 유일한 방법은, 각 고속도로를 두 도시를 잇는 호(arc)로 보고 철도 노선의 북쪽 또는 남쪽 중 한쪽에만 그리는 것이다.

그림 2. 도시 1-2, 1-3, 2-4, 5-7, 4-8, 7-8, 6-8을 잇는 고속도로의 배치 예시 (호는 점선, 철도 노선은 실선).

같은 쪽에 놓인 두 고속도로는 두 도시 구간이 서로 엇갈릴 때에만 교차한다. 즉 한 고속도로의 끝점 중 정확히 하나가 다른 고속도로의 두 끝점 사이에 엄격히 들어갈 때 교차한다. 한 도시를 공유하거나, 한 구간이 다른 구간 안에 포개어지거나, 완전히 떨어져 있는 고속도로들은 서로 교차하지 않으며 같은 쪽에 놓일 수 있다. 서로 반대쪽에 놓인 고속도로는 절대 교차하지 않는다.

바이톨 왕은 어떤 도시 쌍을 이을지 이미 정해 두었다. 어떤 두 고속도로도 교차하지 않도록 각 고속도로를 철도 노선의 북쪽에 놓을지 남쪽에 놓을지 정하거나, 그러한 배치가 존재하지 않음을 보고하라.

첫 번째 줄에 두 정수 $n$과 $k$가 주어진다 ($1 \le n, k \le 20000$). 각각 도시의 수와 건설 예정인 고속도로의 수이다.

이어지는 $k$개의 줄 중 $i$번째 줄에는 두 정수 $p_i$와 $q_i$가 주어진다 ($1 \le p_i < q_i \le n$). $i$번째 고속도로가 잇는 두 도시의 번호이다. 같은 도시 쌍은 중복되지 않는다.

유효한 배치가 존재하지 않으면 IMPOSSIBLE만 한 줄에 출력한다.

배치가 존재하면 $k$개의 줄을 출력한다. $i$번째 줄에는 입력 순서대로 $i$번째 고속도로에 대한 대문자 한 글자를 출력한다. 철도 노선의 북쪽에 건설해야 하면 N, 남쪽에 건설해야 하면 S이다.

여러 배치가 유효할 수 있다. 유효한 모든 배치 중에서 사전순으로 가장 작은 것을 출력한다. $k$개의 글자를 위에서 아래로 읽어 하나의 문자열로 보고, N이 S보다 작다고 간주한다.