HELP THE QUEEN
All submissions for this problem are available.
Queen Victoria, had a precious necklace that was made from beads having themselves made of 2 special types of gems and stones. Also, the beads could fix correctly in the necklace only if the meet of two beads were of same stone.
Such a necklace was rare and precious, but one fine day suddenly it was torn and all the beads were spread all over on the floor in no time.She collected those beads somehow, but she is not sure that she has collected them all.
Now, you are the king and you are asked to fix it. Determine whether it is possible to re-make the necklace for the queen with the available beads.
The input contains T test cases. The first line of the input contains the integer T. The first line of each test case contains an integer N (5 < N < 1000) giving the number of beads the queen was able to collect. Each of the next N lines contains two integers describing the colours of a bead. Colours are represented by integers ranging from 1 to 50.
For each test case in the input first output the test case number as shown in the sample output.
Then if you apprehend that some beads may be lost just print the sentence "some beads may be lost" on a line by itself. Otherwise, print N lines with a single bead description on each line. Each bead description consists of two integers giving the colours of its two ends. 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. Since there are many solutions, any one of them is acceptable. Print a blank line between two successive test cases.
The left value of the first bead in the solution should have least value from all given beads and that set must have the minimum total such possibility.
Input: 2 5 1 2 2 3 3 4 4 5 5 6 5 2 1 2 2 3 4 3 1 2 4 Output: some beads may be lost 2 1 1 3 3 4 4 2 2 2
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, C, C99 strict, CLOJ, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, FORT, FS, GO, ICON, JAVA, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PYTH, PYTH 3.5, RUBY, SCM guile, SCM qobi, ST, TCL|
Fetching successful submissions
If you are still having problems, see a sample solution here.