Phá cạnh

Trong một buổi học về lý thuyết đồ thị, FullHouse Dev được giảng viên giao cho một bài toán thú vị về cây. Với kiến thức về bitwise operations và cấu trúc cây, nhóm bắt đầu tìm hiểu cách giải quyết bài toán này.

Bài toán

Cho một cây (đồ thị vô hướng liên thông không có chu trình) gồm \(N\) đỉnh và các cạnh. Mỗi đỉnh của cây được gán một số nguyên. Bạn có thể chọn phá bất kỳ cạnh nào của cây, việc này sẽ tạo ra 2 cây con từ cây ban đầu.

Gọi \(F(T)\) là phép toán OR bit của tất cả các số được ghi trên mỗi đỉnh trong một cây \(T\).

Nhiệm vụ là tìm số lượng cạnh mà khi phá đi, \(F(T)\) của hai cây con tạo thành sẽ bằng nhau.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(N\) - số đỉnh của cây
• Dòng thứ hai chứa \(N\) số nguyên, số thứ \(i\) biểu thị giá trị được ghi trên đỉnh thứ \(i\)
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(A\) và \(B\), thể hiện có một cạnh nối giữa đỉnh \(A\) và đỉnh \(B\)

OUTPUT FORMAT:

• In ra số lượng cạnh thỏa mãn yêu cầu đề bài

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(0 \leq\) giá trị tại mỗi đỉnh \(\leq 10^9\)

Ví dụ

INPUT

5
2 3 32 43 8
1 2
1 3
2 4
3 5

OUTPUT

1

Giải thích

Bạn có thể phá cạnh nối giữa đỉnh 2 và đỉnh 4.