Even Kingdom 的国王即将去世，他的两个儿子（当然，这是一个偶数）Alfred 和 Brian 对统治王国拥有平等的权利。国王决定将王国分成两部分，以便每个儿子都能独立统治他那一部分。当然，这种分割必须是“偶数”的。

王国由 $n$ 个城市组成，其中一些城市通过双向道路连接；没有道路连接城市自身，也没有两个城市之间有多条道路。分割后，每个城市将归 Alfred 或 Brian 所有。此外，连接属于不同兄弟的城市的每条道路都将被摧毁。如果分割后，在摧毁这些道路的情况下，每个城市仍然直接连接到偶数个其他城市（即，表示道路网络的图中每个顶点的度数都是偶数），那么这种分割就是“偶数”的。

时间紧迫；请帮助这位善良的国王找到他王国的偶数分割方案！

请注意，最初某些城市对之间可能无法通过道路到达，而在偶数分割中，某些部分中的一些城市之间可能也无法通过剩余的道路到达。

输入格式

输入的第一行包含两个空格分隔的整数 $n$ 和 $m$ —— Even Kingdom 中城市和道路的数量（$1 \le n \le 500$，$0 \le m \le \frac{n(n-1)}{2}$）。

接下来的 $m$ 行描述了王国中的道路；这些行中的第 $i$ 行包含两个空格分隔的整数 —— 第 $i$ 条道路连接的城市编号。城市编号从 1 开始。每对城市之间最多只有一条道路，且没有道路连接城市自身。

输出格式

如果分割是可能的，请打印一行包含 $n$ 个字符的字符串；如果第 $i$ 个城市应归 Alfred 所有，则第 $i$ 个字符应为 “A”；如果应归 Brian 所有，则为 “B”。如果有多种可能的答案，输出其中任意一个即可。

如果分割是不可能的，请打印一行 “IMPOSSIBLE”。

样例

样例输入 1

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

样例输出 1

BAAA

样例输入 2

3 3
1 2
2 3
3 1

样例输出 2

AAA

说明

请注意，有可能其中一个兄弟根本分不到任何城市。好吧，没人说过这必须是公平的。