树上询问

Problem Description

给定一个大小为 $n$ 的树，第 $i$ 个节点点权为 $p_i$，其中 $p_1,p_2,\ldots,p_n$ 是一个大小为 $n$ 的排列。接下来你要处理 $m$ 次以下两种操作之一：

• 给定树上两点 $x$ 和 $y$，交换 $p_x$ 和 $p_y$。
• 给定区间 $[l,r]$，询问是否存在树上两点 $x$ 和 $y$，使得 $x$ 到 $y$ 路径上的点权恰好为 $[l,r]$ 区间内所有整数。

Input

输入第一行包含一个整数 $T$ ($1 \le T \le 20$)，表示测试数据的组数。 对于每组测试数据， 输入第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示树的大小。 输入第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$ ($1 \le p_i \le n$)，表示节点的点权。保证 $p$ 是一个大小为 $n$ 的排列。 接下来 $n-1$ 行，每行两个整数 $x_i$, $y_i$ ($1 \le x_i, y_i \le n$)，表示存在一条连接节点 $x_i$ 与节点 $y_i$ 的边。保证所有边构成一棵树。 接下来一行输入一个整数 $m$ ($1 \le m \le 10^5$)，表示操作的数量。 接下来 $m$ 行表示操作，第 $i$ 次操作为两种操作中的一种：

• $1\ x\ y$ ($1\le x,y \le n$)，表示交换节点 $x$ 和 $y$ 的点权。注意， $x$ 和 $y$ 可能相同。
• $2\ l \ r$ ($1 \le l \le r \le n$)，表示询问的区间。

Output

对于每次操作 $2$，输出一行一个字符串 Yes 或 No ，分别表示树上存在/不存在满足条件的节点 $x$ 与 $y$。

Sample Input

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

Sample Output

Yes
No
Yes

Source

2024“钉耙编程”中国大学生算法设计超级联赛（9）