链接: https://cses.fi/problemset/task/1704

板块: Advanced Graph Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

Syrjälä 的网络由 $n$ 台计算机和 $n-1$ 条它们之间的连接构成。任意两台计算机之间都能传输数据。

然而，一旦某条连接断开，某些计算机之间就无法再传输数据。你的任务是新增最少数量的连接，使得即便任意一条连接断开，任意两台计算机之间仍然都能传输数据。

输入

第一行包含一个整数 $n$：计算机数量。计算机编号为 $1,2,\dots,n$。

接下来有 $n-1$ 行描述连接。每行包含两个整数 $a$ 和 $b$：表示计算机 $a$ 与 $b$ 之间有一条连接。

输出

先输出一个整数 $k$：最少需要新增的连接数量。然后输出 $k$ 行描述这些连接。你可以输出任意一组合法解。

数据范围

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

样例输入

5
1 2
1 3
3 4
3 5

样例输出

2
2 4
4 5