题目描述
My little sister had a beautiful necklace made of colorful beads. Each two successive beads in the necklace shared a common color at their meeting point, as shown below:
But, alas! One day, the necklace tore and the beads were scattered all over the floor. My sister did her best to pick up all the beads, but she is not sure whether she found them all. Now she has come to me for help. She wants to know whether it is possible to make a necklace using all the beads she has in the same way that her original necklace was made. If so, how can the beads be so arranged?
Write a program to solve the problem.
输入
The first line of the input contains the integer T, giving the number of test cases. The first line of each test case contains an integer N ( 5<=N<= 1,000) giving the number of beads my sister found. Each of the next N lines contains two integers describing the colors of a bead. Colors are represented by integers ranging from 1 to 50.
输出
For each test case, print the test case number as shown in the sample output. If reconstruction is impossible, print the sentence “some beads may be lost" on a line by itself. Otherwise, print N lines, each with a single bead description such that for 1<=i<=N – 1, the second integer on line i must be the same as the first integer on line i + 1. Additionally, the second integer on line N must be equal to the first integer on line 1. There may be many solutions, any one of which is acceptable.
Print a blank line between two successive test cases.
样例输入
2
5
1 2
2 3
3 4
4 5
5 6
5
2 1
2 2
3 4
3 1
2 4
样例输出
Case #1
some beads may be lost
Case #2
2 1
1 3
3 4
4 2
2 2
参考代码
暂无
解析
暂无
