题目描述

约翰是一个农场主，他的农场有n块田，编号从 $1$到 $n$，这 $n$块田通过 $m$条双向道路相连(数据保证这n块田都是联通的)，我们假设第$i$块田会产生 $2^{i}$kg 的收益，现在约翰想把农田的工作全部交给自己的两个孩子，划分方式必须满足以下规则:

1.每一块田都需要恰好被分给一个孩子.

2.分给两个孩子的农田必须是联通的.就是说对于任意一个孩子在划分给自己的任意一块田，都可以不经过另外一个孩子的田，到达自己的任意一块田.

3.划分给两个孩子的收益必须尽可能的相等，如果无法相等，年长的孩子会得到大的那一份.

对于第 $i$块田，如果你要把它分给年长的孩子，请输出A,否则输出B.

题目输入

第一行输入两个整数分别代表 $n, m$ 接下来 $m$行，每个两个整数$u, v$，代表这两块农田通过一条双向道路直接相连，数据保证没有重边和自环

题目输出

输出一个字符串，代表答案

样例输入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

数据范围

$2 \leq n \leq 3e5, 1 \leq m \leq 3e5$