F. New Year and Social Network
data structures; graph matchings; graphs; math; trees
Donghyun's new social network service (SNS) contains \(n\) users numbered \(1, 2, \ldots, n\). Internally, their network is a tree graph, so there are \(n-1\) direct connections between each user. Each user can reach every other users by using some sequence of direct connections. From now on, we will denote this primary network as \(T_1\).To prevent a possible server breakdown, Donghyun created a backup network \(T_2\), which also connects the same \(n\) users via a tree graph. If a system breaks down, exactly one edge \(e \in T_1\) becomes unusable. In this case, Donghyun will protect the edge \(e\) by picking another edge \(f \in T_2\), and add it to the existing network. This new edge should make the network be connected again. Donghyun wants to assign a replacement edge \(f \in T_2\) for as many edges \(e \in T_1\) as possible. However, since the backup network \(T_2\) is fragile, \(f \in T_2\) can be assigned as the replacement edge for at most one edge in \(T_1\). With this restriction, Donghyun wants to protect as many edges in \(T_1\) as possible.Formally, let \(E(T)\) be an edge set of the tree \(T\). We consider a bipartite graph with two parts \(E(T_1)\) and \(E(T_2)\). For \(e \in E(T_1), f \in E(T_2)\), there is an edge connecting \(\{e, f\}\) if and only if graph \(T_1 - \{e\} + \{f\}\) is a tree. You should find a maximum matching in this bipartite graph.
The first line contains an integer \(n\) (\(2 \le n \le 250\,000\)), the number of users. In the next \(n-1\) lines, two integers \(a_i\), \(b_i\) (\(1 \le a_i, b_i \le n\)) are given. Those two numbers denote the indices of the vertices connected by the corresponding edge in \(T_1\).In the next \(n-1\) lines, two integers \(c_i\), \(d_i\) (\(1 \le c_i, d_i \le n\)) are given. Those two numbers denote the indices of the vertices connected by the corresponding edge in \(T_2\). It is guaranteed that both edge sets form a tree of size \(n\).
In the first line, print the number \(m\) (\(0 \leq m < n\)), the maximum number of edges that can be protected.In the next \(m\) lines, print four integers \(a_i, b_i, c_i, d_i\). Those four numbers denote that the edge \((a_i, b_i)\) in \(T_1\) is will be replaced with an edge \((c_i, d_i)\) in \(T_2\).All printed edges should belong to their respective network, and they should link to distinct edges in their respective network. If one removes an edge \((a_i, b_i)\) from \(T_1\) and adds edge \((c_i, d_i)\) from \(T_2\), the network should remain connected. The order of printing the edges or the order of vertices in each edge does not matter.If there are several solutions, you can print any.