Silva 家族是巴西内陆的一家小麦生产商。他们拥有一个由 Silva 夫妇管理的大型种植园。但这个种植园的形状很奇特：它有 $N$ 个编号从 $1$ 到 $N$ 的田地，由 $M$ 条双向道路连接。为了方便收获季节的工作，种植园的设计使得任意两块田地之间都可以通过现有道路相互到达。此外，由于田地大小不同，每块田地的生产力也不同。第 $i$ 块田地的年小麦产量为 $2^i$ 千克。

随着时间的推移，Silva 夫妇厌倦了打理种植园，决定将这项任务交给他们的两个孩子：Ana 和 Bob。为了避免孩子们之间发生争执，夫妇俩希望按照以下规则划分这 $N$ 块田地：

• 每块田地必须恰好属于一个孩子。
• 属于同一个孩子的任意两块田地之间，必须存在一条仅经过该孩子所属田地的路径。
• 每个孩子所拥有的田地产量之和应尽可能接近。

如果无法将田地划分使得产量之和相等，由于 Ana 是长女，她将获得产量之和较大的一份。

当夫妇俩尝试进行这种划分时，他们意识到这项任务非常复杂，因此他们请求你的帮助。给定田地和道路，你的工作是帮助 Silva 家族按照他们的意愿在两个孩子之间划分田地。

输入格式

第一行包含两个整数 $N$ ($2 \le N \le 3 \times 10^5$) 和 $M$ ($1 \le M \le 3 \times 10^5$)，分别表示田地的数量和道路的数量。接下来的 $M$ 行，每行包含两个整数 $U$ 和 $V$ ($1 \le U, V \le N$ 且 $U \neq V$)，表示田地 $U$ 和 $V$ 之间有一条双向道路。保证任意两块田地之间都可以通过给定的道路相互到达，且任意两块田地之间最多只有一条道路。

输出格式

输出一行长度为 $N$ 的字符串，其中第 $i$ 个字符为大写字母 “A” 或 “B”，分别表示 Ana 或 Bob 应该获得第 $i$ 块田地。如果存在多种解，输出其中任意一种即可。

样例

样例输入 1

3 2
1 3
3 2

样例输出 1

ABA

样例输入 2

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

样例输出 2

BABABA