짝수 분할

짝수 왕국의 선한 왕이 죽음을 앞두고 있고, 두 아들 Alfred와 Brian이 왕국을 다스릴 동등한 권리를 가지고 있다. 왕은 왕국을 둘로 나누어 두 아들이 각자 자신의 몫을 단독으로 다스리게 하려 한다. 물론 그 분할은 짝수여야 한다.

왕국은 $n$개의 도시로 이루어져 있고, 일부 도시 쌍은 양방향 도로로 연결되어 있다. 자기 자신과 이어진 도로는 없고, 두 도시를 잇는 도로가 둘 이상인 경우도 없다. 분할이 끝나면 각 도시는 Alfred 또는 Brian 중 한 명에게 속한다. 또한 서로 다른 형제에게 속한 도시를 잇는 도로는 모두 파괴된다. 그렇게 도로를 파괴한 뒤 모든 도시가 직접 연결된 다른 도시의 수가 짝수이면, 즉 도로망을 나타내는 그래프의 모든 정점의 차수가 짝수이면 그 분할은 짝수이다.

시간이 촉박하다. 선한 왕이 왕국의 짝수 분할을 찾도록 도와라!

처음부터 도로로 서로 오갈 수 없는 도시 쌍이 있을 수 있고, 짝수 분할에서도 어떤 몫의 도시들이 남은 도로로 서로 오갈 수 없을 수 있다.

첫 줄에 짝수 왕국의 도시 수와 도로 수를 나타내는 두 정수 $n$과 $m$이 공백으로 구분되어 주어진다. ($1 \leq n \leq 500$, $0 \leq m \leq \frac{n (n - 1)}{2}$)

다음 $m$개 줄에 왕국의 도로가 주어진다. 이 중 $i$번째 줄에는 $i$번째 도로가 잇는 두 도시의 번호가 공백으로 구분되어 주어진다. 도시 번호는 1부터 시작한다. 어떤 두 도시 사이에도 도로가 둘 이상 존재하지 않고, 자기 자신과 이어지는 도로도 없다.

분할이 가능하면 $n$개의 문자로 이루어진 한 줄을 출력한다. $i$번째 문자는 $i$번째 도시가 Alfred에게 속하면 "A", Brian에게 속하면 "B"이다. 가능한 답이 여러 개라면 그중 아무거나 출력한다.

분할이 불가능하면 한 줄에 "IMPOSSIBLE"을 출력한다.

형제 중 한 명이 도시를 하나도 받지 못할 수도 있다. 뭐, 공평해야 한다고 말한 사람은 없다.

예제 1

입력:

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Expected output:

BAAA

예제 2

입력:

3 3
1 2
2 3
3 1

Expected output:

AAA