"_Houston, are you there? Over._"
"_Yes. Over._"
"_It seems like there is something wrong with our spaceship. Something has got into the ranch near the pointy tip of our spaceship and it is too far for us to put a hand on it. Over._"
"_Copy. There is a metal stick inside the storage of the spaceship. It has been broken down into several pieces for it to be easy to store in the spaceship. You can use it to poke the thing down. Over._"
"_Got it. But how do we assemble it back to one piece? Over._"
"_See the numbers that is written on the two ends. Two ends of two pieces can connect if the numbers written on it is the same. The stick can only be used if all $N$ pieces are assembled back together. Over._"
"_So it works like the game "Domino"? Over._"
"_True. Over._"
You are given all of the $N$ pieces of the sticks, with numbers given for each end of each stick. You have to output one way to put the pieces back together out of possibly many answers. It is guaranteed that there are at least one possible answer.
The first line contains an integer $N$ ($2 <= N <= 8$) - number of pieces that the stick broken down into.
The $i$th line of the next $N$ lines contains two integer $u_i$ and $v_i$ ($1 <= u_i, v_i <= 6$) - numbers written on two ends of piece $i$.
Output $N$ lines. The $j$th line contain two items: an integer $i$, and a letter $c$. The integer $i$ indicates that you use the $i$th piece in the $j$-th place in the configuration, and the letter $c$ indicates that if you decide to put it in the same order as the input ($c =$_'a'_ for this case) or if you want to reverse it ($c =$_'b'_ for this case).
You can output any configuration you want, but you have to make sure that the ends that connect to each other have the same number. Otherwise, you'll get "_Wrong Answer_".
First example: $(2, 3) -(3, 6)$.
Second example: $(4, 4) -(4, 5) -(5, 1) -(1, 3) -(3, 2)$. The first line you can print "_3 a_" instead.
## Input
The first line contains an integer $N$ ($2 <= N <= 8$) - number of pieces that the stick broken down into.The $i$th line of the next $N$ lines contains two integer $u_i$ and $v_i$ ($1 <= u_i, v_i <= 6$) - numbers written on two ends of piece $i$.
## Output
Output $N$ lines. The $j$th line contain two items: an integer $i$, and a letter $c$. The integer $i$ indicates that you use the $i$th piece in the $j$-th place in the configuration, and the letter $c$ indicates that if you decide to put it in the same order as the input ($c =$_'a'_ for this case) or if you want to reverse it ($c =$_'b'_ for this case). You can output any configuration you want, but you have to make sure that the ends that connect to each other have the same number. Otherwise, you'll get "_Wrong Answer_".
[samples]
## Note
First example: $(2, 3) -(3, 6)$.Second example: $(4, 4) -(4, 5) -(5, 1) -(1, 3) -(3, 2)$. The first line you can print "_3 a_" instead.
**Definitions**
Let $ N \in \mathbb{Z} $ be the number of stick pieces, with $ 2 \leq N \leq 8 $.
Let $ P = \{(u_i, v_i) \mid i \in \{1, \dots, N\}\} $ be the set of pieces, where each piece $ i $ has two endpoints labeled $ u_i, v_i \in \{1, \dots, 6\} $.
**Constraints**
1. Each piece $ i $ can be used in original orientation $ (u_i, v_i) $ (denoted 'a') or reversed $ (v_i, u_i) $ (denoted 'b').
2. The assembled sequence must form a linear chain: for consecutive pieces $ j $ and $ j+1 $, the right endpoint of piece $ j $ equals the left endpoint of piece $ j+1 $.
3. All $ N $ pieces must be used exactly once.
**Objective**
Find a permutation $ \sigma : \{1, \dots, N\} \to \{1, \dots, N\} $ and a sequence of orientations $ o_j \in \{\text{'a'}, \text{'b'}\} $ for $ j = 1, \dots, N $, such that:
- The sequence of oriented pieces $ \left( (x_1, y_1), (x_2, y_2), \dots, (x_N, y_N) \right) $ satisfies $ y_j = x_{j+1} $ for all $ j \in \{1, \dots, N-1\} $,
- Where $ (x_j, y_j) = \begin{cases} (u_{\sigma(j)}, v_{\sigma(j)}) & \text{if } o_j = \text{'a'} \\ (v_{\sigma(j)}, u_{\sigma(j)}) & \text{if } o_j = \text{'b'} \end{cases} $.
Output: $ N $ lines, each containing $ \sigma(j) $ and $ o_j $.