Trong bài toán này, chúng ta sẽ xem xét một loại cây nhị phân được gọi là cây boolean. Trong cây này, mọi hàng đều được lấp đầy hoàn toàn, ngoại trừ có thể là hàng cuối cùng (sâu nhất), và các nút ở hàng cuối cùng nằm xa nhất về bên trái có thể. Ngoài ra, mọi nút trong cây sẽ có 0 hoặc 2 con.

Điều làm cho cây boolean trở nên đặc biệt là mỗi nút có một giá trị boolean đi kèm, 1 hoặc 0. Ngoài ra, mỗi nút nội bộ (nút không phải lá) có một cổng "AND" hoặc "OR" đi kèm. Giá trị của một nút cổng "AND" được tính bằng phép AND logic của giá trị hai con của nó. Tương tự, giá trị của một nút cổng "OR" được tính bằng phép OR logic của giá trị hai con của nó. Giá trị của tất cả các nút lá sẽ được cho trong dữ liệu vào để giá trị của tất cả các nút có thể được tính toán ngược lên cây.

Gốc của cây là đối tượng chúng ta đặc biệt quan tâm. Chúng ta rất muốn gốc có giá trị \(V\), là 1 hoặc 0. Tuy nhiên, đây có thể không phải là giá trị thực tế của gốc. May mắn thay, chúng ta có thể gian lận và thay đổi loại cổng cho một số nút; chúng ta có thể đổi cổng AND thành cổng OR hoặc cổng OR thành cổng AND.

Cho mô tả về một cây boolean và những cổng nào có thể thay đổi được, hãy tìm số lượng cổng tối thiểu cần thay đổi để làm cho giá trị của nút gốc trở thành \(V\). Nếu điều này là không thể, hãy xuất "IMPOSSIBLE".

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào chứa số lượng bộ test, \(N\). \(N\) bộ test tiếp theo.

Mỗi bộ test bắt đầu bằng \(M\) và \(V\). \(M\) đại diện cho số lượng nút trong cây và sẽ là số lẻ để đảm bảo tất cả các nút có 0 hoặc 2 con. \(V\) là giá trị mong muốn cho nút gốc, 0 hoặc 1.

\(M\) dòng tiếp theo mô tả từng nút của cây. Dòng thứ \(X\) sẽ mô tả nút \(X\), bắt đầu với nút 1 ở dòng đầu tiên.

\((M-1)/2\) dòng đầu tiên mô tả các nút nội bộ. Mỗi dòng chứa \(G\) và \(C\), mỗi giá trị là 0 hoặc 1. Nếu \(G\) là 1 thì cổng cho nút này là cổng AND, ngược lại là cổng OR. Nếu \(C\) là 1 thì cổng cho nút này có thể thay đổi được, ngược lại thì không. Nút nội bộ \(X\) có các nút \(2X\) và \(2X+1\) là con.

\((M+1)/2\) dòng tiếp theo mô tả các nút lá. Mỗi dòng chứa một giá trị \(I\), 0 hoặc 1, là giá trị của nút lá.

Để giúp hình dung, đây là hình ảnh của cây trong ví dụ đầu tiên.

Dữ liệu ra

Đối với mỗi bộ test, bạn nên xuất:

Case #X: Y

trong đó \(X\) là số thứ tự của bộ test và \(Y\) là số lượng cổng tối thiểu phải thay đổi để làm cho đầu ra của nút gốc là \(V\), hoặc "IMPOSSIBLE" nếu điều này là không thể.

Case #X: Y

Ràng buộc

• \(1 < N \le 20\)

Phân nhóm

• Small dataset (Test set 1): \(2 < M < 30\)
• Large dataset (Test set 2): \(2 < M < 10000\)

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
9 1
1 0
1 1
1 1
0 0
1
0
1
0
1
5 0
1 1
0 0
1
1
0

Case #1: 1
Case #2: IMPOSSIBLE

Nguồn

Google Code Jam 2008, Vòng 2, bài Cheating a Boolean Tree.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.