← 返回题目列表

Codeforces · 1906/I

I. 应急计划 2

中文机器翻译题面 查看原题

您在ICPC 公司担任经理。公司大楼内有$$$N$$$台计算机(编号从$$$1$$$到$$$N$$$)。有 $$$N - 1$$$ 电缆,编号从 $$$1$$$ 到 $$$N - 1$$$,将所有计算机连接到一个网络中。电缆 $$$i$$$ 连接计算机 $$$U_i$$$ 和 $$$V_i$$$。每根电缆都可以设置为紧急模式,其中电缆 $$$i$$$ 仅将数据从计算机 $$$U_i$$$ 传输到计算机 $$$V_i$$$,反之则不然。在灾难期间,所有电缆都必须处于紧急模式。

通过您的研究,您发现了一种确定网络漏洞的新方法。您希望向当前网络添加零个或更多新电缆,以使其在灾难期间不易受到攻击。当且仅当存在 $$$1$$$ 到 $$$N$$$ 的一种排列,使得在连接计算机 $$$u$$$ 和 $$$v$$$ 的所有电缆的排列中,$$$u$$$ 出现在 $$$v$$$ 之前,您的网络才不易受到攻击。换句话说,它应该具有完全相同的拓扑顺序。

下图显示了不易受攻击的网络和易受攻击的网络的示例。

对于不易受攻击的网络,满足左侧和右侧网络要求的唯一排列分别是 $$$[1, 2, 3]$$$ 和 $$$[3, 1, 2]$$$。同时,对于易受攻击的网络,有 $$$2$$$ 排列满足左侧网络的要求:$$$[1, 2, 3]$$$ 和 $$$[3, 1, 2]$$$;而没有满足右边网络要求的排列。

您感兴趣的是应添加到当前网络中的最少数量的新电缆,以使其在灾难期间不易受到攻击。此外,您想知道应使用最少数量的电缆连接哪对计算机。如果有多种连接方式,您可以选择任意一种方式进行连接。在给定的约束下,可以证明存在一种方法使网络不易受到攻击。

输入

第一行由一个整数 $$$N$$$ ($$$2 \leq N \leq 100\,000$$$) 组成。

接下来的 $$$N - 1$$$ 行均包含两个整数 $$$U_i$$$ $$$V_i$$$ ($$$1 \leq U_i, V_i \leq N$$$)。输入边形成一棵树。

输出

第一行由一个整数组成,表示应添加到当前网络中以使其在灾难期间不再脆弱的新电缆的最小数量。将此编号表示为 $$$K$$$,新电缆的编号从 $$$1$$$ 到 $$$K$$$。

如果 $$$K$$$ 不是 $$$0$$$,则输出 $$$K$$$ 行。接下来的 $$$K$$$ 行由两个整数 $$$A_i$$$ $$$B_i$$$ 组成,代表通过新电缆 $$$i$$$ 连接的计算机。在灾难期间,新电缆 $$$i$$$ 仅将数据从计算机 $$$A_i$$$ 传输到计算机 $$$B_i$$$,反之则不然。如果存在多个解,则可以输出其中任何一个。

示例

输入 #1

3
1 2
3 2

输出 #1

1
3 1

输入 #2

3
1 2
2 3

输出 #2

0

输入 #3

5
1 2
1 3
3 4
3 5

输出 #3

2
2 3
4 5

注意

示例输入/输出 #3 的说明

下图显示了灾难期间原始网络和添加了电缆的新网络。满足要求的唯一排列是 $$$[1, 2, 3, 4, 5]$$$。