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