Description

Cool’s trading partners form a tree.

For each trade, there is a start and an end. The path from the start to the end on the tree is called the trade chain. All trading partners (nodes) on the trade chain join this trade, and the cost of the trade equals the number of trading partners on the chain.

Now there are $m$ trades. Cool will designate $k$ trades such that there exists a mysterious trading partner who participates in all these $k$ trades, and he wants to minimize the maximum difference of costs among these $k$ trades (i.e., minimize max cost $-$ min cost).

Input Format

The input consists of several lines.

• The first line contains three integers $n, m, k$, representing the number of trading partners, the number of trades, and the designated $k$.
• Each of the next $n-1$ lines contains two integers $u, v$, indicating that trading partners $u$ and $v$ are connected in the trading tree.
• Each of the next $m$ lines contains two integers $s, t$, representing the start and end of a trade (the start and end may coincide).

Output Format

Output a single integer, the minimal possible value of the maximum cost difference among the designated trades. If no such set of $k$ trades exists, output $-1$.

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

1

Hint

Constraints

$1\leq n\leq 5\times 10^4, 1\leq k\leq m\leq 10^4.$

Sample Explanation

Choose trades $1, 2, 3$. Trading partner $1$ participates in all three trades, and the three costs are $3, 4, 4$. Their maximum cost difference is $4-3$. This is optimal.

Translated by ChatGPT 5