D. It's not Ashamed to Feel Sad
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

反回文串是指对于某个长度为$$$n$$$的字符串$$$s$$$，对于$$$\forall i\in [0,n)$$$，均满足$$$s[i]≠s[n-1-i]$$$。

例如，字符串'codeforces'，'love'是反回文串，但是'you'，'abbc'就不是反回文串。

给你一个 $$$n$$$ 个节点的有根树，树的根节点为$$$1$$$，树的每个节点上有一个小写字母。

有 $$$q$$$ 次询问，每次询问给出两个值$$$now,deep$$$，代表对于节点$$$now$$$，其子树中所有对于根来说深度为$$$deep$$$（根的深度为$$$1$$$）的节点上的字母组成的集合能否构成一个反回文串。

Input

第一行，两个整数 $$$n,q(1\le n \le 2·10^5;1\le q \le 2·10^5)$$$，代表树的节点数与询问数。

接下来的$$$n-1$$$行，每行两个整数 $$$u,v(1\le u,v \le n)$$$，代表树上的一条边，保证最终给出的是一棵树。

接下来的一行，一个长度为$$$n$$$的字符串$$$s$$$，其中$$$s[i-1]$$$代表节点$$$i$$$上的字母。

接下来的$$$q$$$行，每行两个整数 $$$now,deep(1\le now,deep \le n)$$$ ，代表一次询问。

Output

对于每个询问，如果可以构成反回文串，输出'Yes'。 如果这次询问中的 $$$deep \lt dep[now]$$$ 或者深度为$$$deep$$$的子节点不存在或无法构成反回文串，输出'No'。

本题的输出大小写不敏感，即'"YES"'、'"yEs"'等均会被视作肯定的答案。

Example
Input
5 3
1 2
1 3
2 4
2 5
aabcc
1 2
3 3
2 3
Output
Yes
No
No
Note

对于询问 $$$1\ 2$$$，当前可以构成反回文串'ab'。

对于询问 $$$3\ 3$$$，深度为$$$3$$$的子节点不存在。

对于询问 $$$2\ 3$$$，'cc'显然不是反回文串。