Description

In a faraway land, there are $n$ members of parliament. They are having a heated debate about a new amendment to the national referendum act. From Monday to Friday, all members happily come to work and argue all day long. A hardworking journalist takes photos at the workplace every workday each week during the heated debates. In each photo, she captures a pair of members staring angrily at each other. The five photos have been forwarded to you for a full analysis.

In fact, each member belongs to one of two political parties. Let us denote the two parties by the letters A and B. Your task is to determine which party each member belongs to. You must ensure that each member quarrels with at most two distinct members of their own party.

Input Format

The first line contains an integer $n$, the number of members of parliament. The members are numbered from $1$ to $n$.

The next five lines describe the photos taken from Monday to Friday. Each of the five lines contains a list of pairs of members who are quarrelling (staring angrily at each other) in that day's photo. The first number on each line is $p$, meaning there are $p$ quarrels, followed by $p$ pairs of integers in the form k l, indicating that member $k$ and member $l$ are quarrelling. Before each pair of integers, there are two spaces.

Output Format

Output a single line: a string of length $n$ consisting only of the characters A and B. The $i$-th character indicates which party the $i$-th member belongs to in a partition that satisfies the given condition. Since the solution is not unique, output any valid one.

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

ABBBBBA

10
3  1 2  7 3  9 4
3  1 3  7 4  9 5
3  1 4  7 5  9 6
3  1 5  7 6  9 8
3  1 6  7 8  9 10

ABBBBBAAAA

Hint

Constraints

• For $30\%$ of the testdata, $1 \le n \le 15$.
• For $100\%$ of the testdata, $1 \le n \le 2 \times 10^5$.

For every valid $p$, $1 \le p \le \dfrac{n}{2}$.

Notes

Translated from COCI2014-2015 CONTEST #4 T5 SABOR.

Thanks to

Translated by ChatGPT 5