军营选择_腾讯音乐娱乐集团笔试题

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

军营选择规则如下：

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

对于所有的满足 $\mathit w_\mathit k\ =\ \mathit {min}\{\mathit w_\text 1,\ \mathit w_\text 2,\ ...,\ \mathit w_\mathit n\}$ 的候选地 $\mathit k$ 而言，都是最佳军营建造地。

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

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

但是，牛牛只擅长指挥军队，并不精通此法，所以，请你给出任意一种可以达成要求的合法方案。

本题为多组测试数据，第一行输入一个正整数 $\mathit T(\text 1\ \leq\ \mathit T\ \leq\ \text {10} ^ \text 5)$ ，代表测试数据组数。

对于每组测试数据，第一行输入一个正整数 $\mathit n(\text 3\ \leq\ \mathit n\ \leq\ \text {10} ^ \text 5)$ ，代表军营候选地的数量。
接下去 $\mathit n\ -\ \text 1$ 行，每行两个正整数 $\mathit u,\ \mathit v(\text 1\ \leq\ \mathit u,\ \mathit v\ \leq\ \mathit n;\ \mathit u\ \ne\ \mathit v)$ ，代表候选地 $\mathit u,\ \mathit v$ 之间存在一条道路 (无向边)。

数据保证，每组测试数据给出的道路一定可以使 $\mathit n$ 个候选地两两相通，同时，所有测试数据的 $\mathit n$ 之和不会超过 $\text {10} ^ \text 6$ .

对于每组测试数据，输出两行，第一行输出两个正整数 $\mathit u_\text 1,\ \mathit v_\text 1$ ，代表封闭原道路 $\mathit u_\text 1,\ \mathit v_\text 1$ ，这条道路必须存在。
第二行输出两个正整数 $\mathit u_\text 2,\ \mathit v_\text 2$ ，代表增加一条道路 $\mathit u_\text 2,\ \mathit v_\text 2$ ，这条道路必须在原道路中不存在或者已经被封闭。
由于是无向边，所以输出 $\mathit u,\ \mathit v$ 等价于 $\mathit v,\ \mathit u$ .

如果存在多种解，任意输出一种即可，只需要保证满足题意。

第一组测试数据中，最佳选择本就只有一个，所以任选一条道路，封闭后再建造即可。
第二组测试数据中，最佳选择为候选地 $\text 1,\ \text 3$ ，而在封闭 $\text {3 4}$ 之间的道路，再添加 $\text {4 1}$ 之间的道路之后，最佳选择就只有候选地 $\text 1$ .

军营选择

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题