树是没有循环的连通图。
排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 可以任意顺序。例如,$$$[5, 1, 3, 2, 4]$$$ 是一个排列,但 $$$[2, 1, 1]$$$ 不是一个排列(因为 $$$1$$$ 在数组中出现两次),并且 $$$[1, 3, 2, 5]$$$ 也不是一个排列(因为 $$$n = 4$$$,但 $$$5$$$ 出现在数组)。
BrMeast 视频拍摄失败后,Alex 陷入了抑郁。就连他的生日也没有让他高兴。不过,在收到蒂莫菲送来的礼物后,亚历克斯的心情突然好了起来。现在他花了好几天的时间和这位才华横溢的建造者一起玩。最近,他想出了一个不寻常的娱乐方式。
Alex 从他的构造函数中构建了一棵树,由 $$$n$$$ 个顶点组成,编号从 $$$1$$$ 到 $$$n$$$,根位于顶点 $$$1$$$。然后他按某种顺序写下从 $$$1$$$ 到 $$$n$$$ 的每个整数,获得排列 $$$p$$$。之后,Alex 提出了 $$$q$$$ 整数三元组 $$$l、r、x$$$。对于每个三元组,他尝试确定顶点 $$$p_l, p_{l+1}, \ldots, p_r$$$ 中是否至少存在一个顶点 $$$x$$$ 的后代。
顶点 $$$u$$$ 是顶点 $$$v$$$ 的后代当且仅当 $$$\mathrm{dist}(1, v) + \mathrm{dist}(v, u) = \mathrm{dist}(1, u)$$$,其中 $$$\mathrm{dist}(a, b)$$$ 是顶点之间的距离$$$a$$$ 和$$$b$$$。换句话说,顶点$$$v$$$必须位于从根到顶点$$$u$$$的路径上。
Alex 向 Zakhar 讲述了这项娱乐活动。现在亚历克斯告诉他的朋友 $$$q$$$ 如上所述的三倍,希望扎克哈可以检查是否有后代的存在。扎哈尔很困,所以他向你寻求帮助。帮助扎克哈回答亚历克斯的所有问题并最终入睡。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n, q$$$ ($$$1 \le n, q \le 10^5$$$) - 分别是树中的顶点数和问题数。
接下来的 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$),表示顶点 $$$u_i$$$ 和 $$$v_i$$$ 之间有一条边(保证生成的图是一棵树)。
下一行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — 排列 $$$p$$$ (保证从 $$$1$$$ 到 $$$n$$$ 的每个整数恰好出现一次)。
然后按照描述 Alex 问题的 $$$q$$$ 行进行操作。第 $$$i$$$ 行包含三个整数 $$$l, r, x$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le x \le n$$$),如语句中所述。
保证所有测试用例的 $$$n$$$ 总和和 $$$q$$$ 总和不超过 $$$10^5$$$。
输出
对于 Alex 的每个问题,如果所描述的后代存在,则打印“Yes”(不带引号),否则打印“No”(不带引号)。
您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。
示例
输入 #1
3 3 5 1 2 2 3 1 2 3 1 2 2 1 2 3 2 3 1 1 2 3 2 3 3 10 10 2 6 2 7 2 4 1 7 2 8 10 6 8 5 9 4 3 4 10 2 5 9 1 7 6 4 3 8 8 9 8 7 8 1 7 10 6 4 8 9 5 5 10 7 10 1 9 9 2 9 10 6 6 6 2 10 10 6 1 1 1 1 1 1
输出 #1
YES NO YES NO YES NO YES YES YES NO YES YES NO NO NO YES