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$。此时最优。