题目描述

给定一个包含 $n$ 个节点的有根树，根节点是节点1。对于每个节点 $i \in \{2,\ldots,n\}$，其父节点为 $f_i$。一个物体最初位于节点 $1$。

在这个问题中，时间被划分为若干个不重叠的区间。在每个区间 $[l_i, r_i]$ 内，节点 $w_i$ 上会出现一个目标。你可以在任何时刻（包括时刻 $0$）切断树中的任意数量的边，每条边只能被切断一次。

在任何时刻：

• 如果目标存在（当前时间处于某个 $[l_i, r_i]$ 内），并且
• 物体和目标在同一个连通块内，并且
• 物体当前不在目标节点上

那么物体将沿着通往目标的唯一简单路径移动一步。如果物体到达目标节点（或在时刻开始时已经在目标节点上），则视为一次成功相遇。

你的目标是通过切断边的策略，确定物体可以与某个目标成功相遇的最早时刻。如果无法与任何目标相遇，则输出 -1。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$ ($1 \leq n \leq 10^6$, $1 \leq k \leq 10^6$) —— 树的大小和目标区间的数量。

第二行包含 $(n-1)$ 个整数 $f_2, f_3, \ldots, f_n$ ($1 \leq f_i < i$) —— 节点 $2,\ldots,n$ 的父节点。

接下来 $k$ 行，每行包含三个整数 $w_i, l_i, r_i$ ($1 \leq w_i \leq n$, $1 \leq l_i \leq r_i \leq 10^9$) —— 表示在时刻 $[l_i, r_i]$ 区间内，目标出现在节点 $w_i$。

保证所有时间区间按顺序给出且不重叠。即对于每个 $1 \leq 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

5

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

6

5 1
1 2 3 4
3 1 1

-1

解释 #1

在第一个测试用例中，可能的最佳策略之一描述如下：

• 时刻 $1$：物体从节点 $1$ 移动到节点 $4$ 。
  • 移动完成后，我们切断节点 $6$ 和节点 $7$ 之间的边。
• 时刻 $2$ 和 $3$：节点 $4$（物体当前所在的节点）和节点 $8$（目标节点）不连通，因此物体不移动。
• 时刻 $4$：树上没有目标，因此物体也不移动。
• 时刻 $5$：目标恰好出现在物体所在的节点 $4$，导致重合。

可以很容易证明，没有策略允许在时刻 $5$ 之前发生重合。因此，答案是 $5$。