POVEZ

문제

Mirko and Slavko are playing a game. Mirko is the game master, and Slavko is the player. Slavko has a headband over his eyes, so he doesn’t see what Mirko is doing. 

The game is played with N cups numbered 1 through N. At the start of the game Mirko puts a ball in one of the cups (Slavko doesn’t know which one). Then, in one step, Slavko says a letter, 'A' or 'B'. Each time Slavko says a letter, Mirko takes the ball and puts it in one cup (possibly the same cup he took it from). The cup into which Mirko puts the ball is uniquely determined by the current position of the cup and the Slavko’s letter. That is, if the ball is in the cup K, it is moved to either cup A_k or B_k (these numbers are predetermined and Slavko knows them). 

Slavko's task is to move the ball into cup 1, regardless of where Mirko put the ball initially. Write a program which finds any sequence of letters that Slavko has to say in order to move the ball into cup 1. The sequence must be shorter than 10 000 letters. 

입력

The first line of input contains the integer N (1 ≤ N ≤ 500), the number of cups. 

Each of the following N lines contains two integers, the numbers A_k and B_k for one cup. The first of these lines contains A₁ and B₁, the second A₂ and B₂ etc. 

Note: for input data will be such that the solution, although possibly not unique, will exist. 

출력

Output the sequence of A's and B's Slavko should say. 

 

4
1 2
1 3
3 1
1 4

ABA

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

BABAABAB