2Trees

Input/Output: standard input/output

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.