Ngày nào cũng đến bảo tàng với tư cách nhà phê bình nghệ thuật, lại còn không được chạm vào hiện vật, cuối cùng đã trở nên quá sức chịu đựng của bạn. Vì thế, bạn quyết định thử lại sự nghiệp trộm tác phẩm nghệ thuật.¹ Tuy nhiên, sau màn ra mắt thảm họa, lần này bạn quyết tâm xử lý hệ thống camera giám sát.

Bạn đã dùng kỹ năng công nghệ thông tin để xâm nhập hệ thống điều khiển camera. Không may, chính những chiếc camera lại là một phần của tác phẩm nghệ thuật sắp đặt mới mang tên Xanadu, khiến chúng hoạt động khá kỳ lạ. Có \(N\) camera, được đánh số \(1,\ldots,N\), bố trí khắp bảo tàng; một số có thể đã tắt vì lý do nghệ thuật. Các camera được nối bằng \(N-1\) dây sao cho hai camera bất kỳ đều được nối với nhau trực tiếp hoặc gián tiếp. Hệ thống điều khiển có một nút riêng cho mỗi camera. Tuy nhiên, nhấn một nút không chỉ đảo trạng thái bật/tắt của camera tương ứng mà còn đảo trạng thái của tất cả camera nối trực tiếp với nó.²

Bạn lo việc xâm nhập sẽ bị phát hiện nếu tương tác với hệ thống điều khiển quá nhiều. Hãy tính số lần nhấn nút ít nhất cần thiết để tắt tất cả camera.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\), là số camera trong bảo tàng.

Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\) (\(1\le a,b\le N\), \(a\ne b\)), cho biết camera \(a\) và camera \(b\) được nối trực tiếp bằng một dây.

Dòng cuối chứa \(N\) số nguyên. Số thứ \(i\) bằng \(1\) nếu camera \(i\) ban đầu đang bật, và bằng \(0\) nếu camera đó ban đầu đang tắt.

Dữ liệu ra

In một dòng chứa một số nguyên là số lần nhấn nút ít nhất để tắt tất cả camera, hoặc chuỗi impossible nếu không thể tắt tất cả camera.

Ràng buộc

• \(3\le N\le100\,000\).
• \(N-1\) dây nối tạo thành một mạng liên thông.
• Mỗi camera ban đầu có trạng thái \(0\) hoặc \(1\).

Phân nhóm

1. \(5\) điểm: \(N\le20\).
2. \(15\) điểm: \(N\le40\).
3. \(10\) điểm: hai camera \(A\) và \(B\) nối trực tiếp với nhau khi và chỉ khi \(|A-B|=1\).
4. \(40\) điểm: mỗi camera nối trực tiếp với nhiều nhất \(3\) camera khác.
5. \(30\) điểm: không có ràng buộc thêm.

Ví dụ

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

4

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

impossible

Giới hạn

Thời gian: \(1\) giây. Bộ nhớ: \(512\) MiB.