L. Tree Harmony
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the mystical Land of Trees, there exists a rooted tree with $$$n$$$ nodes. The tree is rooted at node $$$1$$$. Each node is uniquely numbered from $$$1$$$ to $$$n$$$, and the tree structure is defined by $$$n-1$$$ edges. Additionally, each node $$$i$$$ has a value $$$a_i$$$.

Two nodes $$$u$$$ and $$$v$$$ are said to be compatible if they satisfy the following conditions:

  1. Let $$$L$$$ be the Lowest Common Ancestor (LCA) of $$$u$$$ and $$$v$$$. For $$$u$$$ and $$$v$$$ to be compatible, $$$u$$$ must be the LCA, i.e., $$$L = u$$$.
  2. Consider the set $$$S$$$, which consists of all nodes in the subtree of $$$u$$$ excluding those in the subtree of $$$v$$$. We must be able to partition $$$S$$$ into two disjoint subsets $$$s_1$$$ and $$$s_2$$$ such that:
    • $$$s_1 \cup s_2 = S$$$, i.e., the union of both subsets must be equal to $$$S$$$,
    • $$$s_1 \cap s_2 = \emptyset$$$, i.e., the subsets must be disjoint, meaning they share no elements.
  3. It must be possible to form pairs between elements of $$$s_1$$$ and $$$s_2$$$ such that each node appears in exactly one pair. A node $$$x$$$ can be paired with a node $$$y$$$ if and only if $$$a_x \neq a_y$$$.

You are given $$$q$$$ queries. In each query, you are given two nodes $$$u$$$ and $$$v$$$, and you must determine whether they are compatible.

Input

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the number of nodes in the tree.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \leq a_i \leq 10^5)$$$ — the values associated with each node.

The next $$$n-1$$$ lines describe the tree structure. Each of these lines contains two integers $$$x$$$ and $$$y$$$ $$$(1 \leq x, y \leq n)$$$, representing an edge between nodes $$$x$$$ and $$$y$$$.

The next line contains an integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ — the number of queries.

The next $$$q$$$ lines each contain two integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n)$$$, representing a query where we must determine if nodes $$$u$$$ and $$$v$$$ are compatible.

Output

For each query, output YES if the nodes $$$u$$$ and $$$v$$$ are compatible; otherwise, output NO. The output is case-insensitive.

Examples
Input
5
1 1 2 1 2
1 2
2 3
3 4
4 5
4
4 5
3 5
2 5
1 4
Output
NO
YES
NO
NO
Input
6
1 2 3 4 5 6
1 2
2 3
3 4
4 5
5 6
4
1 3
1 2
2 5
1 6
Output
YES
NO
NO
NO