Starch Tree Transformation

In this problem, you are given an integer \(n\) and two trees \(T\) and \(S\) (both with vertices numbered from \(1\) to \(n\)). Ysuperman defines a rooted tree \(S\) to be a starch tree of tree \(T\) if and only if the following conditions hold (here, for any node \(i\) in \(S\), denote by \(s_i\) the set of nodes in the subtree of \(S\) rooted at \(i\)):

1. \(S\) and \(T\) have the same \(n\) vertices (numbered \(1\) through \(n\)).
2. For every node \(i\) in \(S\) that has at least one child, and for every child \(j\) of \(i\) (in some chosen rooting of \(S\)), there exists at least one edge in \(T\) connecting \(i\) to some vertex in \(s_j\); that is, \(T\) contains an edge between \(i\) and some vertex in the subtree of \(S\) rooted at \(j\): \(\exists v \in s_j\) such that \((i, v) \in T\).

It is easy to show that a tree \(T\) may have many starch trees. Now, given trees \(T\) and \(S\) (\(S\) is provided without an explicit root) and letting \(d\) be the maximum degree of \(S\), you are required to perform a sequence of operations (at least one and at most \(d\) operations) on \(T\). In each operation, you replace the current \(T\) with any one of its starch trees. Your task is to determine a sequence of operations that will transform the original \(T\) into \(S\) (i.e. the final \(T\) must have the same edge set as \(S\)).

You are guaranteed that at least one valid sequence of operations exists.

inputFormat

The input begins with an integer \(n\) (the number of vertices). The next \(n-1\) lines each contain two integers \(u\) and \(v\), describing an edge of the tree \(T\). The following \(n-1\) lines each contain two integers \(u\) and \(v\), describing an edge of the tree \(S\).

outputFormat

First, output an integer \(k\) (\(1 \le k \le d\), where \(d\) is the maximum degree of \(S\)), representing the number of operations. Then, for each operation, output exactly \(n-1\) lines where each line contains two integers representing an edge of the new tree. The final tree after all operations must have the same edge set as \(S\).

sample

3
1 2
2 3
1 2
1 3

1
1 2
1 3