OI题库

【题目描述】

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”