Chef rất nổi tiếng nên những người bạn thường đến chơi. Bạn của Chef là Pesic quyết định đến thăm anh ta ở Chefland trong chuyến đi vòng quanh thế giới nổi tiếng của mình. Nhưng anh ta lại bị lạc đường và kẹt ở Queryland. Queryland có kiến trúc kỳ lạ: nó có \(N\) thành phố (đánh số từ \(1\) tới \(N\)) và \(N – 1\) con đường hai chiều nối chúng sao cho từ một thành phố có thể tới bất kỳ thành phố nào khác.

Pesic đến thăm tất cả các thành phố của Queryland và gán giá trị cho chúng theo kinh nghiệm của mình. Gọi giá trị ban đầu của thành phố \(i\) là \(A_i\). Giờ Pesic đã biết tất cả các thành phố, anh ta muốn chơi ở Queryland lâu hơn chút. Anh ta có \(Q\) truy vấn gồm \(2\) loại:

• "1 X Y": Gọi đường đi ngắn nhất giữa thành phố \(X\) và \(Y\) là \(L\). Độ dài đường đi là số thành phố bao gồm cả hai điểm đầu cuối. Kiểm tra xem các giá trị của các thành phố trên đường đi (chứa cả hai điểm đầu cuối) tạo thành một hoán vị của các số nguyên từ \(1\) tới \(L\) không.
• "2 X Z": Đổi giá trị của thành phố \(X\) thành \(Z\)

Bạn là một fan của Pesic, nên anh ấy để bạn thực hiện những quy vấn này cho mình.

Dữ liệu vào

• Dòng đầu tiên của dữ liệu vào chứa một số nguyên \(T\) – số test. Test được miêu tả như sau:
• Dòng đầu tiên của mỗi test chứa hai số nguyên \(N\) và \(Q\)
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, …, A_N\)
• \(N – 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) thể hiện thành phố \(u\) và \(v\) được nối với nhau bởi một con đường
• \(Q\) dòng tiếp theo thể hiện các truy vấn:
• Mỗi dòng bắt đầu bằng một số nguyên \(t\) thể hiện loại truy vấn: \(t = 1\) cho truy vấn loại đầu còn \(t = 2\) là cho truy vấn loại hai
• Nếu \(t = 1\), theo sau là hai số nguyên \(X\) và \(Y\) thể hiện truy vấn loại đầu
• Nếu \(t = 2\), theo sau là hai số nguyên \(X\) và \(Z\) thể hiện truy vấn thứ hai

Dữ liệu ra

• Với mỗi truy vấn loại đầu, in ra một dòng chứa xâu "Yes" nếu các giá trị của đường đi đó đúng là một hoán vị hoặc "No" nếu không phải.

Ràng buộc

• \(1 \le T \le 10\)
• \(1 \le N,Q \le 25 \times 10^4\)
• \(1 \le u,v \le N\)
• \(1 \le X,Y,Z \le N\)
• \(1 \le Ai \le N\) với mọi \(i\)
• Tổng của \(N\) trong tất cả các test không vượt quá \(5 \times 10^4\)
• Tổng của \(Q\) trong tất cả các test không vượt quá \(5 \times 10^4\)

Subtasks

• Subtask #1 (10 điểm): N, Q ≤ 1,000
• Subtask #2 (40 điểm): v = u + 1 với mọi con đường
• Subtask #3 (50 điểm): ràng buộc gốc

Input 1

1
10 5
1 2 3 4 5 6 7 8 9 10
1 2
1 3
2 4
2 5
3 9
4 10
5 6
5 7
5 8
1 4 3
1 10 3
2 10 5
1 10 3
1 5 3

Output 1

Yes
No
Yes
No

Giải thích

• Truy vấn \(1\): Giá trị của các thành phố trên đường đi giữa \(4\) và \(3\) là \(4, 2, 1\) và \(3\), nên chúng là hoán vị của \(1,2,3,4\).
• Truy vấn \(2\): Giá trị của các thành phố trên đường đi giữa \(10\) và \(3\) là \(10, 4, 2, 1\) và \(3\), nên chúng không là hoán vị của \(1,2,3,4,5\).
• Truy vấn \(3\): Giá trị của thành phố \(10\) đổi từ \(10\) thành \(5\).
• Truy vấn \(4\): Giá trị của các thành phố trên đường đi giữa \(10\) và \(3\) bây giờ là \(5, 4, 2, 1\) và \(3\), là hoán vị của \(1,2,3,4,5\).
• Truy vấn \(5\): Giá trị của các thành phố trên đường đi giữa \(5\) và \(3\) là \(5, 2, 1\) và \(3\), không là hoán vị của \(1,2,3,4\).