题目描述

给定一棵包含 $n$ 个节点的有根树，根节点是节点 $1$。对于每个节点 $i$（$2\le i\le n$），其父亲节点为 $f_i$，这表示节点 $i$ 和节点 $f_i$ 之间有一条边。棋子最初位于节点 $1$。

在这个问题中，我们认为时间从 $1$ 开始的所有离散时刻。共有 $k$ 个不重叠的时间区间。在每个区间 $[l_i, r_i]$ 内，节点 $u_i$ 上会出现一个目标。你可以在任何时刻（包括时刻 $0$，也可以执行任意多次）切断树中的任意数量的边。一旦一条边被切断，它将被永久移除。

在任意时刻：

$1.$如果目标存在（即当前时间处于某个区间 $[l_i, r_i]$ 内），并且

$2.$棋子和目标在同一个连通块内，并且

$3.$棋子当前不在目标节点上，

那么，棋子将沿着通往目标的唯一简单路径移动一步。如果棋子到达目标节点（或在时刻开始时已经在目标节点上），我们称发生了一次重合。

你的目标是通过选择一套切断边的策略，确定棋子可以重合于某个目标的最早时刻。如果永远无法与任何目标重合，则输出 $-1$。

输入格式

输入的第一行包含两个整数 $n$ 和 $k(1\leq n,k \leq 10^6)$，表示树的大小和时间区间的数量：

第二行包含 $(n-1)$ 个整数 $f_2, f_3, \dots, f_n$（满足 $1 \le f_i < i$），表示节点 $2,\dots,n$ 的父节点。

接下来有 $k$ 行。第 $i$ 行包含三个整数 $u_i, l_i$ 和 $r_i$（满足 $1 \le u_i \le n,\ 1 \le l_i \le r_i \le 10^9$），表示在时刻 $l_i$ 到 $r_i$（包含端点）之间，目标出现在节点 $u_i$ 上。

保证所有时间区间按顺序给出且不重叠；即对于每个 $1 \le i < k$，有 $r_i < l_{i+1}$。

输出格式

输出一个整数：物体可以与目标重合的最小时刻。如果不可能，输出 $-1$。

输入输出样例 #1

输入 #1

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

输出 #1

5

输入输出样例 #2

输入 #2

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

输出 #2

6

输入输出样例 #3

输入 #3

5 1
1 2 3 4
3 1 1

输出 #3

-1

说明/提示

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

时刻 1： 物体从节点 1 移动到节点 4。

移动完成后，我们切断节点 6 和节点 7 之间的边。

时刻 2 和 3： 节点 4（物体当前所在的节点）和节点 8（目标节点）不连通，因此物体不移动。

时刻 4： 树上没有目标，因此物体也不移动。

时刻 5： 目标恰好出现在物体所在的节点 4，导致 重合。

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