6294
内容
79
活动
420181
关注

实验简介

实验后您将收获到

  • 体会构造性证明过程是算法实现过程;
  • 运用DFS编程解决欧拉图问题;
  • 对图进行建模;
  • 回顾等价类和等价关系及其编程实验:并查集。
  1. 学生编程解决如下问题。所完成的程序要在规定的时间和内存限制下,通过官方测试数据,或通过在线测试。
  2. 完成实验报告。

问题描述

我妹妹有一条用彩色珠子做的漂亮项链。每个珠子由两种颜色组成,相继的两个珠子在邻接处共享一种颜色,如图所示:

    有一天,项链线断了,珠子撒了一地。妹妹收集了散落在地上的珠子,但无法肯定是否收齐。她来找我帮忙,想知道用目前收集的珠子是否能够串连成项链。

    请您帮我写一个程序解决这个问题。

输入

    输入包含T 个测试用例,输入的第一行给出整数T。 

    每个测试用例的第一行给出一个整数N (5≤N≤100),表示我妹妹收集到的珠子的数目。接下来的N 行每行包含两个整数,表示一个珠子的两种颜色,颜色用从1到50的整数表示。

输出

    对于输入中的每个测试用例,首先输出测试用例编号,如样例输出;如果无法连成项链,输出一行“some beads may be lost”;否则,输出N行,每行用珠子两端的颜色对应的两个整数描述一颗珠子,在第i行第2个整数要和第i + 1行的第1个整数相同。此外,在第N 行的第2个整数要和第1行的第1个整数相等。可能存在多解,任何一个解都是可接受的。 

在两个连续的测试用例之间输出一个空行。

样例输入

样例输出

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

在线测试:UVA10054,UVA 2036

时限: 1000MS,内存限制:65536 K