← 返回题目列表

Codeforces · 1284/F

F. 新年和社交网络

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

Donghyun 的新社交网络服务 (SNS) 包含 $$$n$$$ 位用户,编号为 $$$1, 2, \ldots, n$$$。在内部,他们的网络是一个树形图,因此每个用户之间有 $$$n-1$$$ 直接连接。每个用户都可以通过使用某种直接连接序列来联系其他所有用户。从现在开始,我们将这个主网络表示为$$$T_1$$$。

为了防止可能的服务器故障,Donhyun 创建了一个备份网络 $$$T_2$$$,该网络还通过树形图连接相同的 $$$n$$$ 用户。如果系统发生故障,则 T_1$$$ 中的一条边 $$$e 将变得无法使用。在这种情况下,Donhyun 将通过选择 T_2$$$ 中的另一条边 $$$f \in 来保护边 $$$e$$$,并将其添加到现有网络中。这个新的边缘应该使网络再次连接。

Donghyun 希望为 T_1$$$ 中尽可能多的边 $$$e \in T_2$$$ 分配替换边 $$$f \in T_1$$$。然而,由于备份网络$$$T_2$$$是脆弱的,所以$$$f \in T_2$$$可以被指定为$$$T_1$$$中最多一条边的替换边。有了这个限制,Donghyun 希望保护 $$$T_1$$$ 中尽可能多的边。

正式地,令 $$$E(T)$$$ 为树 $$$T$$$ 的边集。我们考虑一个由 $$$E(T_1)$$$ 和 $$$E(T_2)$$$ 两部分组成的二部图。对于 $$$e \in E(T_1)、f \in E(T_2)$$$,当且仅当图 $$$T_1 - \{e\} + \{f\}$$$ 是一棵树时,存在连接 $$$\{e, f\}$$$ 的边。您应该在此二分图中找到最大匹配。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 250\,000$$$),用户数量。

在接下来的 $$$n-1$$$ 行中,给出了两个整数 $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$)。这两个数字表示 $$$T_1$$$ 中相应边连接的顶点的索引。

在接下来的 $$$n-1$$$ 行中,给出了两个整数 $$$c_i$$$, $$$d_i$$$ ($$$1 \le c_i, d_i \le n$$$)。这两个数字表示 $$$T_2$$$ 中相应边连接的顶点的索引。

保证两个边集形成大小为 $$$n$$$ 的树。

输出

在第一行中,打印数字 $$$m$$$ ($$$0 \leq m < n$$$),即可以保护的最大边数。

在接下来的 $$$m$$$ 行中,打印四个整数 $$$a_i, b_i, c_i, d_i$$$。这四个数字表示 $$$T_1$$$ 中的边 $$$(a_i, b_i)$$$ 将被 $$$T_2$$$ 中的边 $$$(c_i, d_i)$$$ 替换。

所有打印的边缘都应属于其各自的网络,并且它们应链接到各自网络中的不同边缘。如果从 $$$T_1$$$ 中删除边 $$$(a_i, b_i)$$$ 并从 $$$T_2$$$ 添加边 $$$(c_i, d_i)$$$,则网络应保持连接。打印边的顺序或每条边中顶点的顺序并不重要。

如果有多个解决方案,您可以打印任何一个。

示例

输入 #1

4
1 2
2 3
4 3
1 3
2 4
1 4

输出 #1

3
3 2 4 2
2 1 1 3
4 3 1 4

输入 #2

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

输出 #2

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

输入 #3

9
7 9
2 8
2 1
7 5
4 7
2 4
9 6
3 9
1 8
4 8
2 9
9 5
7 6
1 3
4 6
5 3

输出 #3

8
4 2 9 2
9 7 6 7
5 7 5 9
6 9 4 6
8 2 8 4
3 9 3 5
2 1 1 8
7 4 1 3