406150: GYM102279 H Houston, Are You There?

"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 \le N \le 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 \le u_i, v_i \le 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".

2
3 2
6 3

2 a
1 a

5
3 2
4 5
4 4
5 1
3 1

3 b
2 a
4 a
5 b
1 a

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.