Network Renovation

题目描述

Syrjälä 的网络由 $n$ 台计算机和 $n-1$ 条连接组成。可以在任意两台计算机之间发送数据。 但是，如果任意一条连接断开，将不再可能在某些计算机之间发送数据。你的任务是添加最少数量的新连接，使得即使任意一条连接断开，你仍然可以在任意两台计算机之间发送数据。

输入格式

第一行包含一个整数 $n$：计算机的数量。计算机编号为 1,2,$\dots$, $n$。 接下来有 $n-1$ 行描述连接。每行有两个整数 $a$ 和 $b$：表示在计算机 $a$ 和 $b$ 之间有一条连接。

输出格式

首先输出一个整数 $k$：最少需要添加的新连接数。之后输出 $k$ 行描述这些连接。你可以输出任意一个有效的解。

5
1 2
1 3
3 4
3 5

2
2 4
4 5

提示

$3 \le n \le 10^5$ $1 \le a,b \le n$

标签: CSES1704|高级图论问题

来源

CSES1704|高级图论问题