填空题

军营选择

发布于 2022-03-03 17:15:08

牛牛是一名新晋营长,需要选择军营建造地点,已知一共有 个候选地,编号为 ,有 条道路,使得这 个候选地之间两两可以到达。

军营选择规则如下:

对于其中一个候选地 而言,如果将该地以及其直接相连的道路全都删除,就可以得到若干个连通块,用 记录下其中的最大连通块中的候选地数量。

对于所有的满足 的候选地 而言,都是最佳军营建造地。

由于最佳地点可能不止一个,所以牛牛想要通过一些操作将该地点唯一化:

首先,牛牛会封闭一条已经存在的道路,接着,构建一条新道路,在这两个操作之后,这 条道路依然可以使 个地点两两相通,同时,最佳地点只有一个。

但是,牛牛只擅长指挥军队,并不精通此法,所以,请你给出任意一种可以达成要求的合法方案。 输入描述: 本题为多组测试数据,第一行输入一个正整数 ,代表测试数据组数。

对于每组测试数据,第一行输入一个正整数 ,代表军营候选地的数量。
接下去 行,每行两个正整数 ,代表候选地 之间存在一条道路 (无向边)。

数据保证,每组测试数据给出的道路一定可以使 个候选地两两相通,同时,所有测试数据的 之和不会超过 .输入样例: 2 3 1 2 1 3 4 1 2 1 3 4 3 输出描述: 对于每组测试数据,输出两行,第一行输出两个正整数 ,代表封闭原道路 ,这条道路必须存在。
第二行输出两个正整数 ,代表增加一条道路 ,这条道路必须在原道路中不存在或者已经被封闭。
由于是无向边,所以输出 等价于 .

如果存在多种解,任意输出一种即可,只需要保证满足题意。输出样例 1 2 2 1 3 4 4 1
关注者
0
被浏览
10
知识点
面圈网VIP题库

面圈网VIP题库全新上线,海量真题题库资源。 90大类考试,超10万份考试真题开放下载啦

去下载看看