Even Separation

The good king of the Even Kingdom is dying, and two (surely, an even number) of his sons, Alfred and Brian, are in equal right of ruling the kingdom. The king has decided to separate the kingdom into two parts, so that each son can rule his part single-handedly. Of course, the separation must be even.

The kingdom consists of $n$ cities, some of which are connected by bidirectional roads; no road connects a city with itself, and no two cities are connected by two or more roads. After separation, each city will belong either to Alfred or to Brian. Moreover, every road which connects cities that belong to different brothers will be destroyed. The separation will be even if, after those roads are destroyed, each of the cities will be directly connected to an even number of other cities (that is, the degree of each vertex of the graph representing the road network will be even).

Time is running short; help the good king to find the even separation of his kingdom!

Note that initially some pairs of cities may be unreachable from each other via roads, and in an even separation it may be possible that some cities in some part are unreachable from each other via remaining roads.

The first line of input 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 in the kingdom; $i$-th of these lines contain two space-separated integers --- numbers of the cities connected by $i$-th road. Cities are numbered starting from $1$. There is no more than one road connecting the every pair of cities, and no road connecting a city to itself.

If the separation is possible, print one line containing $n$ characters; the $i$-th character should be "A" or "B" if the $i$-th city should belong to Alfred or Brian, respectively. If there are several possible answers, output any of them.

If the separation is impossible, print one line "IMPOSSIBLE".

Note that it is possible that some of the brothers will not get any cities at all. Oh well, no one said it should be fair.