The edge lists edges1 and edges2 describe two separate undirected trees. The first tree has edges1.length + 1 nodes labeled from 0, and the second has edges2.length + 1 nodes labeled from 0. Labels belong to their own tree; nodes with the same label in different trees are distinct.
Add exactly one new edge connecting a node of the first tree to a node of the second tree. Return the smallest possible diameter of the resulting tree.
A tree's diameter is the number of edges in its longest path between any two nodes. An empty edge list represents a tree with one node.
Example 1:
Input: edges1 = []
edges2 = []
Output: 1Explanation: Each tree contains one node. Connecting those two nodes creates one edge, so the diameter is 1.
Example 2:
Input: edges1 = [[0,1],[1,2]]
edges2 = [[0,1],[1,2]]
Output: 3Explanation: Connect node 1 in the first tree to node 1 in the second. The longest resulting path goes from a leaf in one tree to a leaf in the other and has 3 edges.
Example 3:
Input: edges1 = [[0,1],[1,2],[2,3],[3,4]]
edges2 = []
Output: 4Explanation: Attach the single node of the second tree to node 2 of the first. The original path from 0 to 4 still has length 4, and no longer path is created. No merge can shorten that existing path.
Constraints:
- Each tree contains between
1and100000nodes. edges1.length == n - 1andedges2.length == m - 1.- Every edge contains exactly two integer endpoints.
- Endpoints in the first tree are distinct labels between
0andn - 1. - Endpoints in the second tree are distinct labels between
0andm - 1. - Both edge lists describe connected, acyclic trees.