解题思路

给定一棵以 1 为根的树，每个点携带一个大写字母。对每次询问 $(u,v)$，取树上从 $u$ 到 $v$ 的简单路径，依次读出字母，判断这个序列是否包含子序列 "BUG"；若不包含则输出 YES，否则输出 NO。

核心建模：4 态自动机 + 函数复合

判断序列是否包含 "BUG" 可用一个 4 态自动机线性扫描完成：

• 状态 0：尚未读到 B
• 状态 1：已读到 B，未读到后续 U

题目内容

小美有一个结点总数为 $n$ 且根节点编号为 $1$ 的有根树。

第 $i$ 个结点的编号为 $i$ ,所携带的字母为 $a_i$。

小美是一名程序员,她认为一对 $(u,v)$ 是好对,当且仅当从节点 $u$ 到节点 $v$ 的简单路径上依次拼接得到字符串 $S$ 的子序列中不存在"$BUG$"。

小美会提出 $q$ 次询问,你需要帮助她回答$(u,v)$是不是好对。

子序列:子序列是原始序列的一个子集，其元素顺序保持不变，但可以选择性地删除一些元素。换句话说，子序列是从原始序列中挑选出来的元素集合，这些元素在原始序列中的相对顺序保持一致。

例如:$S=BAUCDEG$,"$BUG$"为字符串 $S$ 的一个子序列,但"$BGA$"不是 $S$ 的子序列。

输入描述

第一行两个整数 $n,q(3 ≤ n,q ≤ 10^5)$,分别表示节点个数和询问次数。

第二行 $n$ 个整数,第 $i$ 个为 $father_i(1 ≤ father_i ≤ i-1)$,表示第 $i$ 个节点的父节点,特别的 $father_1= 0$ 。

第三行 $n$ 个字母,第 $i$ 个为 $a_i('A'≤ a_i<'Z')$,表示第 $i$ 个节点所携带的字母。

接下来 $q$ 行,每行两个墪数 $u,v(1 ≤ u ≠ ≤ n)$,表示询问的起点和终点。

输出描述

共 $q$ 行,每行一个字符串,若 $(u,v)$ 是好对输出"$YES$",否则输出"$NO$"。

样例1

输入

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

输出

NO
YES
YES