Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Discuss Home ProblemSet Status Ranklist Contest LoginRegister Exam
Problem 1087. -- The Necklace

The Necklace

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 2  Solved: 0


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.

Sample Input

1 2
2 3
3 4
4 5
5 6
2 1
2 2
3 4
3 1
2 4

Sample Output

Case #1
some beads may be lost

Case #2
2 1
1 3
3 4
4 2
2 2





한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin