军营选择
发布于 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
军营选择规则如下:
对于其中一个候选地
对于所有的满足
由于最佳地点可能不止一个,所以牛牛想要通过一些操作将该地点唯一化:
首先,牛牛会封闭一条已经存在的道路,接着,构建一条新道路,在这两个操作之后,这
但是,牛牛只擅长指挥军队,并不精通此法,所以,请你给出任意一种可以达成要求的合法方案。 输入描述: 本题为多组测试数据,第一行输入一个正整数
对于每组测试数据,第一行输入一个正整数
接下去
数据保证,每组测试数据给出的道路一定可以使
第二行输出两个正整数
由于是无向边,所以输出
如果存在多种解,任意输出一种即可,只需要保证满足题意。输出样例 1 2 2 1 3 4 4 1
关注者
0
被浏览
10