Cây là một đồ thị vô hướng liên thông và không có chu trình. Một cây có n đỉnh luôn luôn có đúng cạnh. Giữa hai đỉnh bất kì của cây, có một và chỉ một đường đi đơn duy nhất. Đường đi đơn là đường đi chỉ đi qua mỗi đỉnh và mỗi cạnh không quá một lần.
Cho một cây gồm n đỉnh. Các đỉnh được đánh số từ đến . Mỗi đỉnh được tô bởi một trong hai màu đỏ hoặc đen. Ta định nghĩa một vùng cùng màu trên cây là một tập hợp các đỉnh của cây thỏa mãn các tính chất sau:
Tính đơn màu: Mọi đỉnh trong tập đều cùng một màu.
Tính liên thông: Với mọi cặp đỉnh và sao cho , tồn tại một đường đi từ x đến y chỉ đi qua các đỉnh thuộc .
Tính cực đại: Không tồn tại cách thêm một đỉnh vào tập sao cho tập vẫn thỏa mãn hai tính chất trên.
Dễ dàng thấy được trong mọi thời điểm, mỗi đỉnh trên cây thuộc một và chỉ một vùng cùng màu. Bạn muốn tất cả các đỉnh trên cây đều có cùng màu. Để làm được điều này, bạn được thực hiện thao tác sau: Chọn một đỉnh u trên cây, đổi màu tất cả các đỉnh thuộc vùng cùng màu chứa đỉnh u từ đỏ thành đen và ngược lại.
Hãy tìm số thao tác tối thiểu cần thực hiện để tất cả các đỉnh trên cây có cùng màu.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên θ và , lần lượt là số thứ tự của subtask chứa test và số bộ dữ liệu có trong file input này.
Tiếp theo là bộ dữ liệu, mỗi bộ dữ liệu được mô tả theo khuôn dạng sau đây:
Dòng đầu tiên là một dòng trống.
Dòng thứ hai chứa số nguyên là số đỉnh của cây.
Dòng thứ ba chứa số nguyên thể hiện màu của các đỉnh trên cây ở thời điểm ban đầu. Trong đó, thể hiện đỉnh có màu đỏ, thể hiện đỉnh có màu đen.
Trong dòng còn lại, mỗi dòng chứa hai số nguyên và cho biết trên cây có một cạnh nối hai đỉnh và .
Tổng giá trị của trong tất cả các bộ dữ liệu của một file input không quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một số nguyên là số thao tác ít nhất cần thực hiện để tất cả các đỉnh trên cây có cùng màu.
, tồn tại một đường đi từ x đến y chỉ đi qua các đỉnh thuộc .