第一课堂
Current course
Participants
General
Topic 2
Topic 3
Topic 4
Topic 5
Topic 6
Topic 7
Topic 8
Topic 9
Topic 10
Topic 11
Topic 12
Topic 13
Topic 14
Topic 15
Topic 16
Topic 17
Topic 18
Topic 19
Topic 20
[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