#2062. 「HAOI2016」地图

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

一天 rin 来到了一个遥远的都市。这个都市有 n 个建筑,编号从 1 n ,其中市中心编号为 1 ,这个都市有 m 条双向通行的街道,每条街道连接着两个建筑,其中某些街道首尾相连连接成了一个环。

rin 通过长时间的走访,已经清楚了这个都市的两个特点:

  1. 从市中心出发可以到达所有的建筑物。
  2. 任意一条街道最多存在于一个简单环中。

令 rin 心花怒放的是,每个建筑物都会有拉面售卖。拉面有很多不同的种类,但对于 rin 而言只有油腻程度的不同,因此我们把油腻程度相同的拉面看做同一种拉面。由于不同建筑物的拉面的油腻程度可能不同,我们用一个正整数来表示拉面的油腻程度。要知道,拉面可是 rin 的最爱,但是现在到了下班高峰期,都市的交通变得非常的堵塞。rin 只能通过没有被堵死的街道通行,去品尝所在建筑物的拉面。

现在 rin 想知道,如果她正在编号为 x 的建筑物,那么在从市中心到 x 的所有简单路径经过的街道都被堵死的情况下,rin 可以品尝到的拉面中(注意没有出现的拉面是不能算在里面的):

  1. 油腻程度 \leq y 且品尝次数为奇数次的拉面有多少种?
  2. 油腻程度 \leq y 且品尝次数为偶数次的拉面有多少种?

输入格式

第一行两个正整数 n, m ,含义如题所示。

第二行一共 n 个正整数,第 i 个数 a_i 表示第 i 个建筑物出售的拉面的油腻程度。

接下来 m 行,每行两个正整数 x, y ,表示在建筑物 x, y 之间有一条双向通行的街道。数据保证 1 \leq x< y \leq n

接下来一行一个正整数 Q ,表示询问个数。

接下来 Q 行每行三个非负整数 ty, x, y x 表示询问的建筑物编号, y 表示油腻程度的限制, ty=0 时表示询问偶数, ty=1 表示询问奇数。

输出格式

一共 Q 行,对于每个询问输出一个答案。

样例

样例输入

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

数据范围与提示

n \leq 100000, m \leq 150000, Q \leq 100000, a_i \leq 10^6

提示:请注意数据范围中的 \leq ,特殊条件中提到的 y 均为询问中的 y ,对于所有的数据,有 y \leq 10^6