题目背景

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。

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

1

提示

选择第1,2,3三场交易,则交易对象3,4,5被同时交易了3次,且三场交易的代

价分别为3,4,4,他们交易代价之差最大为4 − 3。此时最优。