[URAL 1569]Iset塔上的网络

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file iset.in Output file iset.out

【题目描述】

Iset塔(高度215米,叶卡捷琳堡第二高楼)很快就要投入运营了,但在建筑中还没有安装计算机网络。这个网络应该非常健壮,有许多的分叉。塔中有N个节点,它们应该被连接到网络中。计划用M条无向边连接这些节点,两个节点之间最多只有一条边。为了节省时间,决定只修建必须的N-1条边,而剩余的电线将在开业典礼后铺设。为了让网络高效,它必须满足一个额外条件:它节点之间的最大距离必须尽可能小。两个节点A,B之间的距离是A,B之间路径的边数。

【输入格式】

输入文件的第一行有两个整数N(2<=N<=100)和M(1<=M<=10000)。接下来的M行描述了最初计划的网络。每行有两个整数,即两个直接相连的节点。节点从1到N编号。假定这个网络是连通的,并且没有节点连接到自身。

【输出格式】

输出N-1行,即开业前必须铺设的网络(按照相同的格式)。

【样例输入】

4 4

1 2

2 3

2 4

3 4

【样例输出】

1 2

2 3

2 4

【提示】

对于30%的数据,1<=N<=10

对于100%的数据,范围如题中所示

【来源】

Problem Author: Sergey Pupyrev

Problem Source: The XIIth USU Programing Championship, October 6, 2007

URAL 1569 Networking the “Iset”