Cool loves jiaoyi
题目背景
Cool 交易得十分熟练。现在 Cool 即将参加一场 NOIP 普及组模拟赛。Cool 什么都不会,他将通过交易来获得每一题的题解 / 标程。
题目描述
Cool 的交易对象构成了一个树形结构。
对于每一场轰轰烈烈的交易,都会有一个交易起点和交易终点。在树上从交易起点到交易终点的路径称作交易链,交易链上的所有交易对象都将加入这场交易,交易的代价即为交易对象数。
现在 Cool 面临着 $m$ 场交易,现在 Cool 要钦点 $k$ 场交易,使得存在某个神秘交易对象参与了所有 $k$ 场交易,并且最小化这 $k$ 场交易中代价之差的最大值。
输入输出格式
输入格式
输入包含若干行。
第一行三个整数 $,n,m,k$ 代表交易对象数、交易场数和 Cool 钦定的 $k$。接下来的 $n-1$ 行,每行两个整数 $u,v$ 代表交易对象 $u,v$ 在交易树上相连。
接下来的 $m$ 行,每行两个整数 $s,t$,表示每场交易的交易起点和交易终点(起点终点可以重合)。
输出格式
输出包含一个整数,表示 Cool 钦点的最小的最大代价之差,若不存在这样的 $k$ 场交易,输出 $-1$。
输入输出样例
输入样例 #1
5 4 3
1 2
1 3
1 4
4 5
2 3
3 5
2 5
4 5
输出样例 #1
1
说明
选择第 $1,2,3$ 三场交易,则交易对象 $3,4,5$ 被同时交易了 $3$ 次,且三场交易的代价分别为 $3,4,4$。他们交易代价之差最大为 $4-3$。此时最优。