The Necklace

题目大意：有一种由彩色珠子连接而成的项链。每个珠子的两半由不同颜色组成。如图所示，相邻两个珠子在接触的地方颜色相同。现在有一些零碎的珠子，需要确认它们是否可以复原成完整的项链。 输入格式：输入第一行为测试数据组数 _T_ 。每组数据的第一行是一个整数_N_ (5 ≤ _N_ ≤ 1000 )，表示珠子的个数。接下来的_N_ 行每行包含两个整数，即珠子两半的颜色。颜色用1~50的整数来表示。 输出格式：对于每组数据，输出测试数据编号和方案。如果无解，输出“some beads may be lost”。方案的格式和输入相同，也是一共_N_ 行，每行用两个整数描述一个珠子（从左到右的顺序），其中第一个整数表示左半的颜色，第二个整数表示右半的颜色。根据题目规定，对于1≤i≤_N_-1,第i行的第二个数必须等于第i+1行上的第一个数，且第_N_行的第二个数必须等于第一行的第一个数（因为项链是环形的）。如果有多解，输出任意一组即可。在相邻两组输出之间应有一个空行。 感谢@ty_rj 提供的翻译

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=995 [PDF](https://uva.onlinejudge.org/external/100/p10054.pdf) 



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