2020-01-13 04:15 AKST

Kattis Set 01


2020-01-20 00:30 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -318 days 0:17:36

Time elapsed


Time remaining


Problem G

A land far, far away has N Members of Parliament (MP). They had a turbulent and passionate debate on the law on amendments to the law on a new referendum on referendums. From Monday to Friday, all MPs joyfully came to work and argued all day.

A diligent news reporter photographed MPs at their workplace in the heat of the argument every working day of the week. What she captured on the photos are pairs of MPs fighting and scowling at each other. The five photographs have been forwarded to you for thorough analysis.

It is a fact that each MP belongs to one of the two political parties. Let’s denote them with letters A and B. Your task is to estimate which MP belongs to which party, so that the following holds for your estimation: each MP argued with at most two distinct members of their own party.


The first line of input contains an integer $N$ ($2 \leq N \leq 200\, 000$), the number of MPs. MPs are denoted with numbers from $1$ to $N$.

The following five lines describe the photographs taken from Monday to Friday. Each of the five lines contains the list of pairs of MPs that are arguing on the photograph that day (scowling at each other). Stated first is the number of pairs $P$ ($1 \leq P \leq N/2$), followed by $P$ pairs in the form “$K$ $L$”, where $K$ and $L$ are labels of MPs scowling at each other. Before each pair there is a double space.

Of course, each MP is stated at most once per line, and no MP ever argues with herself.


The first and only line of output must contain an array consisting of only characters A and B, so that the $K$-th character denotes the party of $K$-th MP in a division that satisfies the given conditions.

Since the solution isn’t going to be unique, output any.

Sample Input 1 Sample Output 1
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
Sample Input 2 Sample Output 2
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