Farm Division

Problem Description

John is a farmer. His farm has $n$ fields numbered $1$ to $n$, connected by $m$ bidirectional roads (the data guarantees all $n$ fields are connected). Field $i$ yields a profit of $2^i$ kg. John now wants to hand all the farm work to his two children, under these rules:

1. Every field must be given to exactly one child.
2. The fields given to each child must form a connected component: from any field assigned to a child, he can reach any other of his own fields without passing through the other child's fields.
3. The profits given to the two children should be as equal as possible; if they cannot be equal, the elder child gets the larger share.

For field $i$, output A if it is given to the elder child, otherwise output B.

Input Format

The first line contains two integers $n$ and $m$.

The following $m$ lines each contain two integers $u, v$, meaning these two fields are directly connected by a bidirectional road. There are no duplicate edges or self-loops.

Output Format

Output one string: the answer.

Sample Input 1

3 2
1 3
3 2

Sample Output 1

ABA

Sample Input 2

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

Sample Output 2

BABABA

Constraints

$2 \leq n \leq 3 \times 10^5$, $1 \leq m \leq 3 \times 10^5$.