L. 生活在树上
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

生活在树上——始终热爱大地——升上天空。

给你一棵有 $$$n$$$ 个节点的树，树上的每一个节点处都有一个字符 $$$c$$$，为 "(" 或 ")" 。一共有 $$$q$$$ 次询问，每次询问树上从 $$$u$$$ 到 $$$v$$$ 有向的简单路径中所有节点构成的字符串 $$$s$$$ 是否是好的。

树上的一条从 $$$u$$$ 到 $$$v$$$ 有向的简单路径是指由一条由树上许多条连续的边组成的路径，第一条边从 $$$u$$$ 出发，最后一条边到达 $$$v$$$，并且该路径只经过树上每个点最多一次。

定义这样的一个只由字符 "(" 和 ")" 组成字符串 $$$s$$$ 是好的: 开始时，你在 $$$s$$$ 的第一个字符上，结束时，你必须站在 $$$s$$$ 的最后一个字符上。在每一个时刻你可以向左移动一个空格（如果你没有站在第一个字符上），或向右移动一个空格（如果你没有站在最后一个字符上）。你不能停留在同一个地方，但可以访问任何字符，包括第一个和最后一个字符，访问次数不限。在每个时间点，你都要写下当前所站的字符。如果存在某种移动序列，能让你从第一个字符走到最后一个字符，从而使你写下的字符串是一个匹配的括号序列，那么我们就说这个字符串 $$$s$$$ 是好的。

所谓匹配的括号序列，是指可以通过在序列的原始字符之间插入字符 "1" 和 "+"，将其转换为正确算术表达式的括号序列。例如，括号序列 "()()"、"(())" 就是匹配的括号序列（得到的表达式为"(1)+(1)"、"((1+1)+1)"），而 ")(" 和 "(" 则不是。

例如，字符串 "()(())))" 是好的，因为在每个时刻，你可以按照 $$$[1,2,3,4,3,4,5,6,7,8]$$$，这样的顺序在字符串上移动，最终的序列为 "()(((())))"，是一个匹配的括号序列。 而字符串 "())(()()(())" 就不是好的，可以确定的是，在每个时刻不论你如何再这个字符串上移动，都不可能得到一个匹配的括号序列。

Input

第一行，一个整数 $$$n(1\le n \le 2·10^5)$$$，代表树的结点数。

接下来的 $$$n-1$$$ 行，每行两个数字 $$$u,v(1\le u,v \le n;u\neq v)$$$，代表树上的一条边，保证最终构成一棵树。 接下来的一行，为一个长度为 $$$n$$$ 只由字符 "(" 和 ")" 组成字符串 $$$s$$$，$$$s_i$$$ 代表树上第 $$$i$$$ 个节点上的字符 $$$c$$$。

下一行，一个整数 $$$q(1\le q \le 2·10^5)$$$，代表询问的次数。

接下来连续的 $$$q$$$ 行，每行两个整数 $$$u,v$$$，代表一次询问树上从 $$$u$$$ 到 $$$v$$$ 有向的简单路径中所有节点构成的字符串 $$$s$$$ 是否是好的。

Output

共 $$$q$$$ 行，如果上从 $$$u$$$ 到 $$$v$$$ 有向的简单路径中所有节点构成的字符串 $$$s$$$ 是好的，那么输出一行 "YES" ,否则，输出一行 "NO"。

你可以输出 "YES "和 "NO" 的任何大小写形式（例如，字符串 "yES"、"yes "和 "Yes" 都将被当作肯定的答案）。

Examples
Input
8
1 2
3 1
4 1
2 5
8 4
5 6
7 5
)()((())
7
5 7
7 5
5 3
6 7
4 8
2 8
2 3
Output
Yes
No
Yes
No
Yes
Yes
No
Input
20
12 5
17 18
18 2
8 19
19 1
14 9
8 15
3 12
18 7
8 14
18 4
14 6
14 10
7 11
8 3
14 13
13 16
8 17
8 20
)((()()())(((((())))
20
15 19
16 5
13 20
8 17
13 20
11 5
11 5
13 19
3 5
14 5
15 7
6 5
3 18
11 20
11 19
14 17
6 17
8 19
11 20
15 18
Output
No
No
No
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
No
Yes
No
Yes