# F.凑热闹的小C

## 题目描述

$\hspace{15pt}$有 $n$ 个城市，编号为 $1$ 到 $n$。其中，城市 $1$ 为首都。每个城市 $i$ 有一个繁华程度 $w_i$。城市之间有 $m$ 条无向道路，保证图连通。  
$\hspace{15pt}$小C喜欢凑热闹，他会从指定城市出发，访问所有可达城市。  
$\hspace{15pt}$现在有 $q$ 次<b>独立</b>询问，第 $i$ 次询问给出三个整数 $x_i,a_i,b_i$，按顺序执行：  
${\hspace{20pt}}_\texttt{1.}\,$删除所有首都 $1$ 到城市 $x_i$ 的<u>简单路径</u>上的道路；保证 $x_i\neq1$；  
${\hspace{20pt}}_\texttt{2.}\,$小C从城市 $x_i$ 出发，访问所有能到达的城市；  
${\hspace{20pt}}_\texttt{3.}\,$将访问过的城市按繁华程度分组，相同繁华程度视为同一种类型；  
${\hspace{20pt}}_\texttt{4.}\,$统计繁华类型为区间 $[a_i,\dots,b_i]$ 的组中，有多少个组中是有城市的？
$\hspace{15pt}$你需要对每次询问分别输出答案。  

【名词解释】
$\hspace{15pt}$<u>简单路径</u>：从节点 $u$ 出发，以节点 $v$ 为终点，随意在图上走，不经过重复的点和边走出来的序列。在本题中，先找到全部简单路径，再进行删除操作。

## 输入描述

$\hspace{15pt}$第一行输入两个整数 $n,m \left(1\leq n\leq 10^5;\ n-1\leq m\leq 2\times 10^5\right)$，分别表示城市数、道路数。  
$\hspace{15pt}$此后 $m$ 行，第 $i$ 行输入两个整数 $u_i,v_i \left(1\leq u_i,v_i\leq n;\ u_i\neq v_i\right)$，表示城市 $u_i$ 与 $v_i$ 间有一条无向道路连接。
$\hspace{15pt}$第 $m+2$ 行输入 $n$ 个整数 $w_1,w_2,\dots,w_n \left(1\leq w_i\leq 10^5\right)$，表示每个城市的繁华程度。

$\hspace{15pt}$第 $m+3$ 行输入一个整数 $q\ \left(1\leq q\leq 10^5\right)$，表示询问数。  
$\hspace{15pt}$此后 $q$ 行，第 $i$ 行输入三个整数 $x_i,a_i,b_i \left(2\leq x_i\leq n,\ 1\leq a_i\leq b_i\leq 10^5\right)$，表示第 $i$ 次查询的条件。

## 输出描述

$\hspace{15pt}$对于每一次询问，新起一行。输出一个整数，表示范围内有多少个组中是有城市的。

## 样例

~~~text input:#1
5 4
1 2
2 3
3 4
4 5
1 2 3 2 1
2
3 2 3
2 1 5
~~~

~~~text output:#1
2
3
~~~

$\hspace{15pt}$在这个样例中，初始的城市构造如下图所示。

<center><img src="https://uploadfiles.nowcoder.com/images/20250512/0_1747050982668/4C1E1784C9EEDAD7C479428F613FBFD8" style="width: 400px;"></center>

$\hspace{15pt}$对于第一次询问：   
$\hspace{23pt}\bullet\,$删除经过城市 $1$ 和 $3$ 的简单路径上的道路后，剩余道路为 $3\!-\!4$ 和 $4\!-\!5$ 两条；   
$\hspace{23pt}\bullet\,$小C从 $3$ 出发，可以访问到城市 $\{3,4,5\}$，繁华程度依次为 $\{3,2,1\}$；   
$\hspace{23pt}\bullet\,$繁华程度为 $2$ 和 $3$ 的组中，均有城市，故答案为 $2$。

~~~text input:#2
5 5
1 2
2 3
3 4
4 5
1 5
1 2 2 3 2
2
2 2 2
5 1 5
~~~

~~~text output:#2
1
1
~~~

$\hspace{15pt}$在这个样例中，初始的城市构造如下图所示。

<center><img src="https://uploadfiles.nowcoder.com/images/20250512/0_1747050862682/DA0E2F56E739600E72542312C12C1460" style="width: 400px;"></center>

$\hspace{15pt}$对于第一次询问：   
$\hspace{23pt}\bullet\,$删除经过城市 $1$ 和 $2$ 的所有简单路径上的道路后，城市 $2$ 只能访问自身，繁华程度为 $\{2\}$；   
$\hspace{23pt}\bullet\,$繁华程度为 $2$ 的组中，均有城市，故答案为 $1$。
  
$\hspace{15pt}$对于第二次询问：   
$\hspace{23pt}\bullet\,$删除经过城市 $1$ 和 $5$ 的所有简单路径上的道路后，城市 $5$ 只能访问自身，繁华程度为 $\{2\}$；   
$\hspace{23pt}\bullet\,$繁华程度为 $1$ 到 $5$ 的组中，仅有 $2$ 有城市，故答案为 $1$。