Minimizing Trade Cost Difference with a Common Trading Object

Cool's trading objects form a tree structure. For each trade, two nodes are given: a starting node and an ending node. The unique simple path from the start to the end is called the trade chain, and the trade cost is defined as the number of nodes on this chain.

Cool is faced with m trades. He now wants to select exactly k trades such that there exists at least one mysterious trading object (i.e. a node in the tree) that appears on the trade chain of every selected trade. Among all possible selections fulfilling this requirement, he wishes to minimize the maximum difference between the trade costs of the chosen trades. In other words, if the costs of the chosen trades are sorted as \(c_1\le c_2\le \dots \le c_k\), he wants to minimize \(c_k-c_1\).

If no such selection exists, output -1.

Note: The distance (number of edges) between two nodes is computed using their lowest common ancestor (LCA). The cost of a trade between nodes \(u\) and \(v\) is \(\mathrm{dist}(u,v)+1\), which is the number of nodes on the unique path from \(u\) to \(v\). All formulas are given in LaTeX format.

inputFormat

The input begins with an integer n (the number of nodes in the tree). Then follow n-1 lines, each containing two integers u and v which indicate an edge between node u and node v.

The next line contains two integers m and k where m is the number of trades and k is the number of trades to be selected.

Then follow m lines, each with two integers representing the starting and ending nodes of a trade.

outputFormat

Output a single integer, which is the minimized maximum difference among the costs of the selected k trades that share at least one common node in their trade chain. If no valid selection exists, output -1.

sample

5
1 2
1 3
2 4
2 5
3 2
4 3
5 3
4 5

0