Bài tập này được chấm theo batch.

Đối với mỗi người trong chúng ta, ai cũng đã trải qua những ngày Tết đoàn viên bên gia đình, người thân bạn bè. Tết, không chỉ là thời điểm để ta tụ họp lại với nhau mà còn là lúc để ta nhìn lại những việc đã qua trong năm vừa rồi. Vào dịp Tết, người Việt vẫn lưu truyền các truyền thống từ xa xưa như làm bánh chưng, bánh dày; đi chùa ngày Tết; hay sắm mai, đào về nhà để trang trí cho đẹp mắt; cúng tổ tiên... Những phong tục này mang lại cho ta không khí Tết ấm cúng, vui vẻ cùng gia đình, và hơn hết, phần được nhiều bạn nhỏ yêu thích nhất, đó chính là phần phát lì xì. Ý nghĩa lì xì ngày Tết là cầu chúc may mắn, sức khỏe và tài lộc cho mọi người. Đây cũng là dịp mà con cháu trong nhà chúc Tết đến ông bà, cha mẹ và nhận lì xì mừng tuổi. Phong bao lì xì màu đỏ bên trong có số tiền nhỏ tượng trưng cho lời chúc may mắn, mạnh khỏe, gặp nhiều thành công trong công việc, học tập mà người lớn muốn gửi đến trẻ.

Và Gấu cũng thế, tuy rất hứng thú với việc nhận lì xì ngày Tết, nhưng nay Gấu đã trưởng thành (đã qua ~17~ tuổi, trải qua hai kì thi HSGQG vô cùng đau khổ) do đó, đến lượt Gấu phát lì xì cho các bạn. Trong các bạn mà Gấu phát ngày hôm nay, có một bạn tên Ngốc và một chị tên Ngốc, hai người tuy không quen biết gì nhau cả, nhưng đều có một mục đích chung đó là dành được càng nhiều tiền lì xì của Gấu thì càng tốt (à còn có một thói quen chung là hay nhịn ăn và thức khuya). Để dành được nhiều tiền lì xì của Gấu, thì hai người phải trả lời hết tất cả các câu hỏi mà Gấu đưa ra, cụ thể như sau:

Gấu vừa mua một cây mai siêu to khổng lồ có tổng cộng ~N~ bông hoa đang nở rộ để về nhà trang trí Tết. Các bông hoa được kết nối với nhau bằng đúng ~N-1~ cành cây sao cho luôn tồn tại một đường đi đơn giữa hai bông hoa bất kì, mỗi bông hoa đều được đánh số theo độ phát triển của hoa để tiện bề chăm sóc, cụ thể bông hoa thứ ~i~ có số thứ tự là ~P_i~. Trên cây mai này, Gấu thực hiện ~Q~ thao tác trang trí và chăm sóc cây như sau:

• ~1~ ~U~ ~V~: Nhận thấy rằng bông hoa thứ ~U~ và ~V~ đã phát triển đạt yêu cầu, do đó, Gấu quyết định đánh số lại hai bông hoa này bằng cách hoán đổi hai số thứ tự của chúng với nhau.
• ~2~ ~U~ ~V~: Các bông hoa trên đường đi đơn từ ~U~ đến ~V~ sẽ được Gấu sắp xếp lại và đem tặng cho các em bé ngoan, vì để tạo sự đầy đủ, ấm no khi biếu quà, Gấu thấy rằng mình sẽ nên tặng các bông hoa liên tiếp nhau, do đó, Gấu cần sẽ thêm một bông hoa có độ phát triển bằng ~M~ sao cho trên đường đi đơn từ ~U~ đến ~V~ thì không xuất hiện bông hoa có độ phát triển bằng ~M~. Hãy tìm số nguyên không âm ~M~ nhỏ nhất có thể. Kí hiệu số nguyên ~M~ thỏa mãn như vậy là ~M =MEX(U, V)~.
• ~3~ ~M~: Hãy đếm số cặp ~(U, V)~ mà ~MEX(U, V) = M~. Lưu ý rằng hai cặp ~(U, V)~ và ~(V, U)~ được xem là như nhau.

Nhắc lại:

• Đường đi đơn giữa hai đỉnh ~\mu~ và ~\nu~ là dãy ~\chi_1, \chi_2, \dots, \chi_\kappa~ sao cho ~\chi_1 = \mu, \chi_\kappa = \nu~ và luôn tồn tại cạnh nối trực tiếp giữa ~\chi_\iota~ và ~\chi_{\iota+1}~ ~0 < \iota < \kappa~.

Dữ liệu vào

• Dòng đầu gồm số nguyên ~\theta~ mô tả thứ tự subtask chứa test này ~(1 \leq \theta \leq 7)~.
• Dòng thứ hai gồm hai số nguyên dương ~N, Q~ ~(1 \leq N, Q \leq 2*10^5)~.
• Dòng thứ ba gồm ~N~ số nguyên ~P_1, P_2, \dots, P_N~ là hoán vị của ~N~ số ~0, 1, \dots, N - 1~.
• Dòng thứ tư gồm ~N-1~ số nguyên ~F_2, F_3, \dots, F_N~ mô tả một cạnh nối giữa hai đỉnh ~(F_i, i)~ trên cây ~(1 \leq F_i < i)~.
• ~Q~ dòng sau, mỗi dòng gồm một truy vấn thuộc một trong ba loại ~(1 \leq U, V \leq N, 0 \leq M \leq N)~.

Dữ liệu ra

In ra đáp án với mỗi truy vấn loại $2$ hoặc loại $3$, các đáp số được in trên cùng một dòng.

Ví dụ

Đầu vào

1
7 7
2 0 3 1 4 5 6 
1 2 2 4 3 4 
2 1 5
2 6 7
3 0
3 1 
1 1 7
2 6 7
3 2

Đầu ra

3
2
10
6
4
8

Giải thích

• Với truy vấn đầu tiên, tập giá trị đã xuất hiện là ~\{0, 1, 2, 4\}~, do đó ~MEX(1, 5) = 3~.
• Với truy vấn thứ hai, tập giá trị đã xuất hiện là ~\{0, 1, 3, 5, 6\}~, do đó ~MEX(6, 7) = 2~.
• Với truy vấn thứ ba, ~10~ đường đi đơn có thể là: ~(1, 1); (3, 3); (4, 4); (5, 5); (6, 6); (7, 7); (4, 5); (4, 7); (5, 7); (3, 6)~.

Tính điểm

Tổng điểm của bài này là ~150~ điểm gồm ~7~ subtasks như sau:

• Subtask ~1~ ~(12~ điểm~)~: ~1 \leq N, Q \leq 50~.
• Subtask ~2~ ~(15~ điểm~)~: ~1 \leq N, Q \leq 300~.
• Subtask ~3~ ~(19~ điểm~)~: ~F_i = i - 1~ ~\forall 1 \leq i \leq N~.
• Subtask ~4~ ~(21~ điểm~)~: ~F_i = 1~ ~\forall 1 \leq i \leq N~.
• Subtask ~5~ ~(25~ điểm~)~: Không có truy vấn loại ~1~ và ~3~.
• Subtask ~6~ ~(25~ điểm~)~: Không có truy vấn loại ~3~.
• Subtask ~7~ ~(33~ điểm~)~: Không có ràng buộc gì thêm.