Mysterious Memory: Maximum Tree Distance

A poor OI contestant, temporaryDO, attempted the partial scoring (when \(k=0\)) of the "Link-Cut Tree" problem in an exam. The \(k=0\) subtask asks for the longest chain on a tree \(T\), but temporaryDO could not solve it. In his frustration, he implemented an \(O(n^2\log n)\) solution by enumerating all pairs of points and computing distances using LCA. However, due to an off‐by-one error in his array allocation, he inadvertently accessed a mysterious memory region that happened to store another tree \(T'\). As a consequence, when computing the distance between vertices \(x\) and \(y\), his program actually computed

[ \mathrm{dist}(x,y)=\mathrm{depth}_T(x)+\mathrm{depth}_T(y)-\Bigl(\mathrm{depth}T(\mathrm{LCA}T(x,y))+\mathrm{depth}{T'}(\mathrm{LCA}{T'}(x,y))\Bigr), ]

and finally output the maximum such "distance" over all pairs \(i, j\) with \(i \le j\). Given two trees \(T\) and \(T'\) with \(n\) vertices (both trees are rooted at vertex 1), please help temporaryDO compute the output of his program.

inputFormat

The first line contains an integer \(n\) \((2 \le n \le 2000)\) representing the number of vertices in each tree. The next \(n-1\) lines describe the first tree \(T\). Each of these lines contains two integers \(u\) and \(v\) indicating an edge between vertices \(u\) and \(v\). The following \(n-1\) lines describe the second tree \(T'\) in the same format. Both trees are undirected and can be considered rooted at vertex 1 (with \(\mathrm{depth}(1)=0\) in each tree).

outputFormat

Output a single integer, the maximum value of \(\mathrm{depth}_T(x)+\mathrm{depth}_T(y)-(\mathrm{depth}_T(\mathrm{LCA}_T(x,y))+\mathrm{depth}_{T'}(\mathrm{LCA}_{T'}(x,y)))\) among all pairs \(1 \le x \le y \le n\).

sample

3
1 2
1 3
1 2
2 3

1