#1483. BEAUTSET - Tập hợp đẹp

Cho một cây có đỉnh đánh số từ đến và đỉnh là gốc. Mỗi đỉnh trên đều được tô màu, đỉnh thứ được tô bởi màu .

Một tập hợp các đỉnh trên được gọi là đẹp nếu có hơn một nửa số đỉnh trong tập được tô bởi cùng một màu.

Có truy vấn, mỗi truy vấn thuộc một trong các dạng sau:

• Truy vấn dạng: , truy vấn này kiểm tra xem tập đỉnh gồm các đỉnh nằm trong cây con gốc có phải là một tập đẹp hay không;
• Truy vấn dạng: , truy vấn này kiểm tra xem tập đỉnh gồm các đỉnh nằm ngoài cây con gốc có phải là một tập đẹp hay không;
• Truy vấn dạng , truy vấn này kiểm tra xem tập đỉnh gồm các đỉnh nằm trên đường đi đơn từ tới (tính cả và ) có phải là một tập đẹp hay không.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương là số đỉnh của cây và số lượng truy vấn;
• Dòng thứ hai chứa số, số thứ là mô tả màu sắc của đỉnh ;
• dòng tiếp theo, mối dòng chứa hai số nguyên dương mô tả cạnh nối hai đỉnh và ;
• Tiếp theo gồm có dòng mô tả các truy vấn. Các truy vấn thuộc một trong ba dạng như mô tả ở trên.

Dữ liệu ra:

• Ghi ra dòng, mỗi dòng chứa một số nguyên là kết quả của truy vấn. Nếu truy vấn đang xét có quá nửa số đỉnh được tô cùng màu, in ra giá trị của màu đó. Ngược lại, in ra .

Ví dụ:

Dữ liệu vào:

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

Dữ liệu ra:

1
-1
-1
3
2

Giải thích:

Dưới đây là hình vẽ của ví dụ thứ nhất với màu được tô màu xám, màu được tô màu đỏ và màu được tô màu xanh.

• Truy vấn : xét các đỉnh trong cây con gốc là , màu xuất hiện lần;
• Truy vấn : xét các đỉnh trên đường đi từ đến là , không có màu nào xuất hiện quá lần;
• Truy vấn : xét các đỉnh nằm ngoài cây con gốc là , không có màu nào xuất hiện quá lần;
• Truy vấn : xét các đỉnh nằm ngoài cây con gốc là ${1, 2, 3, 4, 7}33$ lần;
• Truy vấn : xét các đỉnh nằm trên đường đi từ đến là , màu xuất hiện lần.

Giới hạn:

• Subtask ;
• Subtask và mỗi đỉnh có tối đa cạnh nối trực tiếp;
• Subtask và ;
• Subtask và không có truy vấn loại ;
• Subtask không có ràng buộc nào thêm.