Even Separation

The good king of the Even Kingdom is dying, and two of his sons, Alfred and Brian, have an equal right to rule the kingdom. The king has decided to split the kingdom into two parts so that each son can rule his part alone. Of course, the split must be even.

The kingdom has $n$ cities, some pairs of which are connected by bidirectional roads. No road connects a city to itself, and no two cities are connected by more than one road. After the split, each city belongs either to Alfred or to Brian. Every road connecting cities that belong to different brothers is then destroyed. The split is even if, after those roads are destroyed, every city is directly connected to an even number of other cities, that is, if every vertex of the graph representing the road network has even degree.

Time is short. Help the good king find an even separation of his kingdom.

Some pairs of cities may be unreachable from each other by roads to begin with, and in an even separation some cities within one part may be unreachable from each other by the remaining roads.

The first line contains two space-separated integers $n$ and $m$, the number of cities and roads in the Even Kingdom ($1 \leq n \leq 500$, $0 \leq m \leq \frac{n (n - 1)}{2}$).

The next $m$ lines describe the roads. The $i$-th of these lines contains two space-separated integers, the numbers of the cities connected by the $i$-th road. Cities are numbered starting from 1. No pair of cities is connected by more than one road, and no road connects a city to itself.

If a separation is possible, print one line of $n$ characters. The $i$-th character is "A" if the $i$-th city belongs to Alfred and "B" if it belongs to Brian. If there are several possible answers, print any of them.

If no separation is possible, print one line containing "IMPOSSIBLE".

One of the brothers may receive no cities at all. Nobody ever said it had to be fair.