Migrated from Lutece 2938 九把七鸡五连鸡

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

8------10------9------75------啥意思。

810975，新人怎么听不懂，810975，怎么就你一个听不懂。

喊什么你为什么打出2连8喊什么这战绩配过情人节吗喊什么没见过这么菜的大鸟喊什么~没见过就去长长见识。

你去看嘛，见没见过，8月10号------9把7鸡5连鸡，多么傲人的战绩------9把7鸡5连鸡，这个必须靠实力------9把7鸡5连鸡，状态好**清醒------9把7鸡5连鸡，好好研究下我的运营。

三连鸡------比比皆是------四连鸡------不足挂齿------多得是------靠运气------最多2连鸡。

我建议你去看一下8月10号打了9盘吃了7鸡5连鸡都懒得提~，鄙人一点小小的成绩，懒得提~，我非常低调拒绝装逼，懒得提~，有些水友老是要念叨，懒得提~，这只是我的冰山一角。

你去看嘛，见没见过，8月10号------9把7鸡5连鸡，多么傲人的战绩------9把7鸡5连鸡，这个必须靠实力------9把7鸡5连鸡，状态好**清醒------9把7鸡5连鸡，好好研究下我的运营。

房间号改成什么，改810975，密码忘了怎么办，试试810975，......

---

这段rap出自《810975》，他说的对，但是前面忘了，中间忘了，所以这个题希望你做什么事呢？

给一棵 $n$ 个点的树和一个正整数集合 $S$ ，树上每个点都有一个权值，权值在 $[1,n]$ 范围内，而集合初始包含 $[1,n]$ 内的所有正整数。有 $q$ 次操作或询问，如下：

1. 对于指定的一个数 $x$ ，若 $x \notin S$ 则把 $x$ 添加到 $S$ 中，否则把 $x$ 从 $S$ 中去除。

2. 将 $u$ 和 $v$ 的最短路径上（包括端点）所有出现的权值构成的集合记为 $S'$ ，求 $\lvert S\cap S' \rvert$ 。

保证操作 $1$ 的出现次数不超过 $1000$ 。

Input

第一行一个整数 $n$ ，表示树的点数。

第二行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示 $i$ 号点的点权。

接下来 $n-1$ 行每行两个整数 $u$ 和 $v$ ，表示 $u$ 和 $v$ 之间连了一条边。

接下来一行一个整数 $q$ 表示询问个数。

接下来 $q$ 行每行代表一个询问，格式具体如下：

对于操作 $1$ ： $1\;\; x$ ，表示改变数 $x$ 在 $S$ 中出现与否的状态。

对于询问 $2$ ： $2\;\; u\;\; v$ ，表示询问的两点为 $u$ 和 $v$ 。

Output

对于每个询问 $2$ ，输出相应的答案。

Samples

5
1 2 3 1 3
1 2
1 3
2 4
2 5
5
2 1 1
2 3 4
1 1
2 4 4
2 3 4

1
3
0
2

Constraints

保证 $1 \le n \le 10^5, 1 \le a_i \le n, 1 \le u\; v \le n, 1 \le q \le 10^5, 1 \le x \le n$ ，另外保证操作 $1$ 的出现次数不超过 $1000$ 。

Resources

2023 UESTC ICPC Training for Data Structures