Description

One day, rin came to a distant metropolis. The city has $n$ buildings, numbered $1$ to $n$, with the city center being building $1$. There are $m$ bidirectional streets, each connecting two buildings, and some streets connect end to end to form a cycle.

After long observation, rin has learned two facts about this city:

1. From the city center, all buildings are reachable.
2. Any street belongs to at most one simple cycle.

Every building sells ramen. There are many kinds of ramen, but for rin only the greasiness level matters, so we treat ramen with the same greasiness level as the same type. We use a positive integer to denote the greasiness level.

It is rush hour, and traffic is very jammed. rin can only travel along streets that are not blocked.

Now rin wants to know: if she is at building $x$, and all streets lying on every simple path from the city center to $x$ are blocked, then among the ramen she can taste (note that types that do not appear at all must not be counted):

1. How many types have greasiness $\leq y$ and appear an odd number of times?
2. How many types have greasiness $\leq y$ and appear an even number of times? Here “even” means a positive even number of occurrences; types with zero occurrences are not counted.

Constraints:

• $n \leq 100000$, $m \leq 150000$, $Q \leq 100000$, $A_i \leq 10^6$.

Input Format

• The first line contains two positive integers $n, m$.
• The second line contains $n$ positive integers; the $i$-th number $A_i$ is the greasiness level of the ramen sold at building $i$.
• The next $m$ lines each contain two positive integers $x, y$, meaning there is a bidirectional street between buildings $x$ and $y$. It is guaranteed that $1 \leq x < y \leq n$.
• The next line contains a single positive integer $Q$, the number of queries.
• The next $Q$ lines each contain three non-negative integers $ty, x, y$. When $ty = 0$, it asks for the count of types with an even number of occurrences; when $ty = 1$, it asks for the count of types with an odd number of occurrences.

Output Format

Output $Q$ lines. For each query, output a single integer: the answer to that query.

10 12
1 10 4 5 2 10 1 8 4 8
1 2
1 3
1 4
2 5
4 6
4 7
7 8
2 9
8 10
1 6
8 10
4 7
10
0 3 9
1 7 6
0 5 2
1 10 9
0 5 7
1 7 4
0 7 3
1 2 7
0 3 4
0 3 8

0
1
0
1
0
1
0
2
0
0

Hint

Please pay attention to the $\leq$ in Constraints. The $y$ mentioned above is the $y$ in the queries. For all testdata, $y \leq 10^6$.

Translated by ChatGPT 5