P3363 Cool loves jiaoyi

Cool is very skilled at trading. Now Cool is about to take part in a NOIP Junior mock contest. Cool knows nothing, so he will obtain each problem’s editorial / standard solution through trading.

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).

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 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$.

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