You are given two undirected trees with $n$ and $m$ nodes, labeled from $0$ to $n - 1$ and $0$ to $m - 1$, respectively.

You are given two $2$D integer arrays edges1 of length $n - 1$ and edges2 of length $m - 1$, where edges1[i] = [a_i, b_i] denotes an edge between nodes a_i and b_i in the first tree, and edges2[i] = [u_i, v_i] denotes an edge between nodes u_i and v_i in the second tree. You are also given an integer k.

A node $u$ is considered a target to node $v$ if the distance between them is at most k.

For each node $i$ from $0$ to $n - 1$, you must add exactly one undirected edge connecting node $i$ in the first tree to any node in the second tree.

Return an array answer of size $n$, where answer[i] represents the maximum possible number of target nodes from node $i$ after adding the optimal edge between node $i$ and the second tree.

Note: The distance between two nodes is defined as the number of edges on the path connecting them. A node is always a target to itself since the distance is $0$.

Constraints:

• $2 \leq n, m \leq 1000$

• edges1.length $== n - 1$

• edges2.length $== m - 1$

• edges1[i].length $==$ edges2[i].length $== 2$

• edges1[i] $= [a_i, b_i]$

• $0 \leq a_i, b_i < n$

• edges2[i] $= [u_i, v_i]$

• $0 \leq u_i, v_i < m$

• The input is generated such that edges1 and edges2 represent valid trees.

• $0 \leq k \leq 1000$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.