Political Party Assignment

In a distant land, there are \(n\) councillors who debated passionately over a referendum amendment on a new law. From Monday to Friday, all councillors attended work and argued vigorously. Each day, a diligent journalist captured a photograph showing a pair of councillors engaged in a heated argument, glaring at each other. You are given 5 such photographs. In fact, each councillor belongs to one of two political parties, denoted by \(A\) and \(B\).

Your task is to determine an assignment of parties for each councillor such that for every councillor \(i\), if we denote by \(S(i)\) the set of distinct councillors from the same party with whom \(i\) had a conflict, then the following condition holds:

\[ |S(i)| \le 2 \]

You may assume that a solution always exists.

inputFormat

The input consists of 6 lines:

1. The first line contains an integer \(n\) (\(1 \le n \le 10^5\)) representing the total number of councillors.
2. The next 5 lines each contain two space‐separated integers \(u\) and \(v\) (\(1 \le u, v \le n,\; u \neq v\)) which indicate the indices of the councillors captured in the photograph for that day.

outputFormat

Output a single line containing a string of length \(n\). The \(i\)th character of the string must be either A or B, representing the political party assigned to the \(i\)th councillor.

sample

3
1 2
2 3
1 3
1 2
2 3

AAB