## Welcome To SDIBT ACM-ICPC Online Judge

Problem 1087. -- The Necklace## The Necklace

Time Limit: 1 Sec Memory Limit: 64 MB

Submit: 2 Solved: 0

[Submit][Status][Discuss]## Description

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.

## Input

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.

## Output

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

2
5
1 2
2 3
3 4
4 5
5 6
5
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

## HINT

## Source

[Submit][Status][Discuss]

HOME
Back

한국어 中文 English

All Copyright Reserved 2008-2010 SDIBT TEAM

GPL2.0 2003-2010 HUSTOJ Project TEAM

Anything about the Problems, Please Contact Admin:admin