题目描述

给定一棵以节点 $1$ 为根的包含 $n$ 个节点的树。对于每个节点 $i$ （ $2 ≤ i ≤ n$ ），其父节点记为 $f_i$ ，表示节点 $i$ 与 $f_i$ 之间有一条边。初始时，一个棋子位于节点 $1$ 。

本题中，时间从 $1$ 开始离散递增。共有 $k$ 个互不重叠的时间区间 $[l_i,\ r_i]$ ，每个区间内会有一个目标出现在节点 $u_i$ 。你可以在任意时刻（包括时刻 $0$ ）切断任意数量的树边（允许多次操作），且切断的边将永久移除。

在任意时刻：

则棋子会沿着唯一简单路径向目标节点移动一步。若棋子到达目标节点（或初始时已在目标节点），则视为一次命中。

你的任务是：通过策略性切断边，确定棋子能够命中任一目标的最早可能时刻。若无法命中任何目标，输出 $-1$ 。

输入格式

第一行：两个整数 $n$ 和 $k$ （ $1 ≤ n,\ k ≤ 10^6$ ），分别表示树的大小和区间数量。

第二行： $n-1$ 个整数 $f_2,\ ...,\ f_n$ （ $1 ≤ f_i < i$ ），表示节点 $2$ 到 $n$ 的父节点编号。

接下来 $k$ 行：每行三个整数 $u_i,\ l_i,\ r_i$ （ $1 ≤ u_i ≤ n$ ， $1 ≤ l_i ≤ r_i ≤ 10^6$ ），描述第 $i$ 个目标出现的节点及时间区间。

保证所有区间按顺序给出且互不重叠，即对任意 $1 ≤ i < k$ ，满足 $r_i < l_{i+1}$ 。

输出一个整数：命中目标的最早时刻；若不可能，输出 $-1$ 。

8 3
1 1 1 4 4 6 7
5 1 1
8 2 3
4 5 5

在第一个测试案例中，一种可能的最优策略描述如下：

时刻 $1$ ：棋子从节点 $1$ 移动到节点 $4$ 。移动完成后，我们切断节点 $6$ 和 $7$ 之间的边。

时刻 $2$ 和 $3$ ：由于棋子所在的节点 $4$ 与目标节点 $8$ 不连通，棋子保持不动。

时刻 $4$ ：树上没有目标出现，棋子依然保持静止。

时刻 $5$ ：目标恰好出现在棋子所在的节点 $4$ ，达成命中条件。

可以证明，不存在任何策略能在时刻 $5$ 之前实现命中。因此，该案例的答案为 $5$ 。