33OJ
登录 注册

#P4665. [BalticOI 2015] Network

    ID: 5400 远端评测题 1000ms 500MiB 尝试: 0 已通过: 0 显示难度提高 上传者: 标签>图论贪心2015Special Judge构造BalticOI(波罗的海)

[BalticOI 2015] Network

题目描述

Byteland 政 府已经决定,现在是时候将他们的小国家与互联网连接起来,以便所有公民都能参加编程竞赛,观看可爱猫的视频。当是时候建设这个国家的网络骨干时,他们指派了 Internet Optimists 公司来连接 Byteland 的所有 NN 个计算机。这些连接以计算机对之间的直接链接建立,使任何一对计算机都通过一系列的链接连接起来。

Byteland 无论如何都不是一个富裕的国家,因此,为了将成本降到最低,网络拓扑是以树的形式构建的(即有 N−1N-1 个计算机之间的直接连接)。为时已晚,人们意识到这一解决方案存在严重缺陷。只要有一个链接断开,那么 Byteland 的计算机就会被分割,这样一些计算机就不能互相通信了!为了提高 Byteland 网络的可靠性,人们决定至少要容忍单个链路中断。你的任务是帮助 Internet Optimists 公司以最便宜的方式改进网络。给定 Byteland 的网络拓扑(即 N−1N-1 个通过直接链接连接的计算机对),求需要添加链接的最少数量,使得如果任何单个链接中断,网络仍将被连接。

输入格式

输入的第一行包含一个正整数 N(N≥3)N(N\geq 3),表示 Byteland 的计算机数量。为了简单起见,所有的计算机编号为 11 到 NN。

接下来 N−1N-1 行每行包含两个整数 aa 和 b(1≤a,b≤n,a≠b)b(1\leq a, b\leq n, a\neq b),它描述计算机 aa 和 bb 之间的直接链接。

输出格式

在输出的第一行只有一个整数 kk,表示应该添加到网络中的最少链接数量。

接下来 kk 行,每行两个整数 aa 和 b(1≤a,b≤n,a≠b)b(1\leq a ,b\leq n,a\neq b) 表示应该通过链接连接的计算机。链接可以按任何顺序输出。如果有一个以上的解决方案,您的程序应该输出其中的任何一个。

6
1 2
2 3
2 4
5 4
6 4
2
1 5
3 6

提示

3≤N≤5×1053 \le N \le 5 \times 10^5。