n cities numbered 0 to n - 1, the second has m cities numbered 0 to m - 1. The roads of each kingdom form a tree: roads_a[i] = [a, b] is a road between cities a and b of the first kingdom, and roads_b[i] = [u, v] is a road in the second.
Call city y handy for city x if the path from x to y uses an even number of roads. A city is always handy for itself.
For each city i of the first kingdom you may build one bridge between any city of the first kingdom and any city of the second. Return an array answer of length n where answer[i] is the largest number of cities, in both kingdoms together, that are handy for i when the bridge is chosen as well as possible. Each i is answered on its own: the bridge is taken down before the next one.roads_a=[[0, 1], [1, 2]], roads_b=[[0, 1], [0, 2], [0, 3]] → [5, 4, 5]
In the first kingdom, city 0 reaches 0 and 2 at even distance, while city 1 reaches only itself. In the second it is best to link to city 0, whose three neighbours then sit at an even distance. The result is [5, 4, 5].
roads_a=[[0, 1]], roads_b=[[1, 0]] → [2, 2]
Each city of the first kingdom counts only itself, and the second kingdom adds one more city: [2, 2].
roads_a=[[0, 1], [0, 2], [2, 3], [3, 4]], roads_b=[[0, 1], [1, 2]] → [4, 5, 5, 4, 5]
len(roads_a) = n - 1, len(roads_b) = m - 1a, b < n; 0 ≤ u, v < mroads_a=[[0, 1], [1, 2]], roads_b=[[0, 1], [0, 2], [0, 3]]
[5, 4, 5]
Run checks the first 3 tests in your browser. Submit checks all 52 tests on the server, hidden ones included.