Migrated from Lutece 2983 简单图论题

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

verjun 有一张 $n$ 个点 $m$ 条边的无向图，已知图联通且任意一条边只会存在在一个简单环内，点的编号为 $1$ 至 $n$，每个点有点权。 你需要处理 $q$ 次询问，每次询问给定两个数 $x,y$，接下来你需要删去所有从 $x$ 号点到 $1$ 号点的简单路径上的边。 考虑删边以后 $x$ 能到达的所有点，你需要统计每一种出现过的权值的出现次数，并回答如下询问：

• 满足 $\le y$ 且出现次数为奇数次的权值有多少种；
• 满足 $\le y$ 且出现次数为偶数次（不能是 $0$）的权值有多少种。

询问之间的删边操作相互独立

Input

第一行两个正整数 $n,m(1\le n\le 10^5,1\le m\le 1.5\times 10^5)$，代表图的点数，边数。 第二行 $n$ 个正整数，第 $i$ 个数 $a_i(1\le a_i\le 10^6)$ 代表 $i$ 号点的权值。 接下来 $m$ 行每行两个数 $x,y$，代表图上有一条连接 $x,y$ 的无向边。 接下来一个正整数 $q(1\le q\le 10^5)$，代表询问次数。 接下来 $q$ 行每行三个整数 $op, x, y$，$x,y$ 代表题述变量，$op=0$ 表示询问偶数，$op=1$ 表示询问奇数。

Output

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

Samples

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

Resources

2023 UESTC ICPC Training for Graph