408909: GYM103379 E Grandest Wreath
Description
The winter season fills Meredith's heart with joy and warmth, and there is no better outlet for her to express her appreciation apart from constructing the most magnificent holiday wreath! In fact, Meredith wants to make as large a wreath as possible, given her materials. She has plucked two branches from a tree and will construct her wreath by attaching the two branches together, using two small and flexible twigs. Help Meredith make the biggest wreath possible!
InputThe first line of input will contain an integer $$$V_1$$$ ($$$1 \leq V_1 \leq 10^6$$$) denoting the number of vertices in Meredith's first branch. $$$V_1 - 1$$$ lines follow, each containing two space-separated integers $$$u$$$ and $$$v$$$ which represent endpoints for an edge in the tree. (Observe that, in general, any tree with $$$n$$$ vertices has exactly $$$n - 1$$$ edges). Then the next line of input contains $$$V_2$$$ ($$$1 \leq V_2 \leq 10^6$$$), the number of the vertices in the second branch. $$$V_2 - 1$$$ lines follow after that, containing the edges for the second tree. You are guaranteed that the depth of either tree (from any root) will not exceed $$$50$$$.
OutputPrint the length of the longest simple cycle Meredith could create by connecting her two branches (trees) with two edges.
ExampleInput7 4 6 2 3 1 7 7 2 5 1 4 7 5 3 2 2 4 5 3 3 1Output
9