403750: GYM101257 B 2Trees

You are given two trees with the same number of leaves L, your task is to merge the two trees' leaves in a way that ensures the following:

• The number of colors needed to color the resulting graph such that no two adjacent nodes share the same color is minimum.
• Each leaf in the first tree is merged into exactly one leaf from the second tree.
• Each leaf in the second tree is merged into exactly one leaf from the first tree.
• Nodes other than leaves are not merged.

Note that by merging two leaves a and b, the resulting node will have both edges of a and b.

The first line of input contains one integer N (3 ≤ N ≤ 10⁵), the number of nodes in the first tree.

Then follows N - 1 lines, the i^th line contains two integers u and v (1 ≤ u, v ≤ N), the indices of the nodes connected by the i^th edge in the first tree.

The next line contains an integer M (3 ≤ M ≤ 10⁵), the number of nodes in the second tree.

Then follows M - 1 lines, the i^th line contains two integers u and v (1 ≤ u, v ≤ M), the indices of the nodes connected by the i^th edge in the second tree.

It is guaranteed that the two trees will have the same number of leaves L.

On a single line print the number of colors needed to color the resulting graph.

Followed by L lines, the i^th line of them contains two integers u and v (1 ≤ u ≤ N)(1 ≤ v ≤ M), the indices of the leaves to be merged, where u is a leaf in the first tree, and v is a leaf in the second tree.

If there’s more than one possible solution, print any of them.

3
1 2
1 3
3
3 1
2 3

2
2 1
3 2

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

3
4 2
1 3

• A tree of N nodes is a connected undirected graph with N - 1 edges.
• A node is a leaf if and only if it is connected to at most one other node.

In the first sample, the two trees can be illustrated as follows:

After merging node 2 from first tree with node 1 from the second tree, and node 3 from the first tree with node 2 from the second tree, the resulting graph is illustrated in the figure below:

The minimum number of colors required to satisfy the problem constraints is 2.