题目描述

给定一棵 $n$ 个点的树，现有一旅行者在第 $0$ 天从点 $s$ 出发。

假定他的移动速度是 $t$，那么他一天内能从 $u$ 走到任意满足 $dist(x,y)≤t$ 的点 $y$。其中 $dist(x,y)$ 为 $x$ 和 $y$ 间最短路径经过的边数。

一条合法的旅行线路需要满足 $m$ 条限制 $T_i,U_i,D_i$，表示旅行者在第 $T_i$ 天所在的点 $u$ 必须满足 $dist(u,U_i)≤D_i$。

问：$t$ 至少为多少，旅行者才能计划一条合法的旅行线路？

输入格式

第一行，$n,m,s$;

下 $n−1$ 行，每行 $2$ 个整数 $u,v$，表示 $u$ 和 $v$ 间连有一条边;

下 $m$ 行，每行 $3$ 个整数，表示 $T_i,U_i,D_i$。

输出格式

一个整数表示答案。

5 3 1
1 2
1 3
2 4
2 5
3 4 1
5 3 0
6 5 1

2

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

1

数据范围

对于所有数据满足 $1≤n≤2·10^5,1≤T_i≤10^9,1≤D_i≤n$。$T_i$ 单调递增。

本题共 $20$ 个测试点，从 $1$ 开始标号。若 $i$ 的二进制表示第 $j$ 位为 $1$，则数据 $i$ 满足性质 $j$。