Sample Input 1

2
1 5 10
7 8 2

Sample Output 1

3

Đề bài

Alice vừa tìm thấy một cuộn băng dính mới, và hôm nay cô ấy đặc biệt hạnh phúc vì cô ấy cũng đã tìm thấy lịch Mùa vọng của em gái mình.

Lịch Mùa vọng có thể được biểu diễn dưới dạng một bảng có ~n~ hàng và ~m~ cột. Mỗi ô vuông chứa một cửa sổ nhỏ, và đằng sau mỗi cửa sổ là một miếng sô cô la. Em gái của Alice đã mở một số cửa sổ và những cửa sổ khác vẫn đang đóng.

Alice quyết định dùng băng dính của mình để dán tất cả các cửa sổ đã đóng lại. Đoạn băng dài vô hạn, và nó rộng bằng một ô lịch. Alice có thể xé một đoạn băng và sử dụng nó để dán một số chuỗi ô cửa sổ đóng liền kề theo chiều ngang hoặc chiều dọc. Cô ấy không muốn đặt nhiều hơn một mảnh băng trên cửa sổ nào đó.

Alice đang tự hỏi số lượng mảnh băng tối thiểu mà cô cần để dán tất cả các cửa sổ đã đóng lại là bao nhiêu.

Input

Vào từ file văn bản LICHMUAVONG.INP:

• Dòng đầu tiên chứa các số nguyên ~n~ và ~m~ (~1 \leq n \leq 1000, 1 \leq m \leq 10~), kích thước của lịch Mùa Vọng.
• Mỗi dòng trong số ~n~ dòng sau chứa ~m~ ký tự '.' và '#' đại diện cho lịch Mùa Vọng. Các ký tự '.' biểu thị một cửa sổ đang mở và ký tự '#' biểu thị một cửa sổ đã đóng.

Output

Đưa ra file văn bản LICHMUAVONG.OUT:

• Đưa ra số lượng mảnh băng tối thiểu cần thiết để dán tất cả các cửa sổ đã đóng.

Ví dụ

Sample Input 1

2 3
#.#
###

Sample Output 1

3

Giới hạn

• Thời gian: ~2.0s~
• Bộ nhớ: ~256M~
• Có 35% số test ứng với 35% số điểm của bài có mỗi cửa sổ đã đóng sẽ liền kề với nhiều nhất hai cửa sổ khác đóng.
• Có 30% số test khác ứng với 35% số điểm của bài có ~1 \leq n \leq 10~.
• Có 35% số test khác ứng với 30% số điểm của bài không có ràng buộc thêm.

Ghi chú

Giải thích ví dụ 1: Sử dụng một miếng băng dính cho cột đầu tiên, một miếng cho cột thứ ba và một miếng cho ô ở hàng thứ hai và cột thứ hai.

Đề bài

Bạn được cung cấp một chuỗi gồm ~N~ ký tự ~0~ hoặc ~1~, được đánh số từ ~1, 2, \dots, N~. Ban đầu mỗi ký tự đại diện cho một chuỗi có độ dài một. Trong quá trình nối, hai từ ~a~ và ~b~ được chọn, xóa và được thay thế bởi chuỗi tạo ra bằng cách ghép chuỗi ~a~ đứng trước chuỗi ~b~.

Chuỗi ban đầu tạo ra ~N~ chuỗi đơn và dần được kết nối thành một chuỗi cuối cùng bằng cách sử dụng ~N - 1~ phép nối. Phép nối thứ ~i~ được mô tả bằng một cặp chỉ mục ~(a_i, b_i)~, biểu thị rằng chuỗi thứ ~a_i~ và chuỗi thứ ~b_i~ sẽ được nối với nhau. Luôn đảm bảo rằng các ký tự có chỉ số ~a_i~ và ~b_i~ không nằm trong cùng một chuỗi.

Giá trị Palindromic của một chuỗi ~w~ được định nghĩa là tổng số chuỗi con duy nhất của ~w~ là chuỗi đối xứng. Chuỗi con của một chuỗi là các chuỗi giống nhau khi đọc từ trái sang phải và phải sang trái. Chuỗi con của một chuỗi được định nghĩa là một chuỗi có được bằng cách xóa không hoặc một số ký tự khỏi đầu và cuối của chuỗi.

Đối với mỗi phép nối, hãy in ra giá trị palindromic của chuỗi kết quả.

Input

• Dòng đầu tiên chứa số nguyên ~N~ (~1 \leq N \leq 100000~), số ký tự.
• Dòng thứ hai chứa chuỗi ~N~ ký tự ~0~ và ~1~.
• ~N - 1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i, b_i~ (~1 \leq a_i, b_i \leq N~, ~a_i \neq b_i~) đại diện cho phép nối thứ ~i~.

Output

• In ra ~N - 1~ dòng, dòng thứ ~i~ là giá trị palindromic của chuỗi sau phép nối thứ ~i~.

Ví dụ

Sample Input 1

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

Sample Output 1

2
2
2
3
4
6
8

Giới hạn

• Thời gian: 2.0s
• Bộ nhớ: 256M

Ghi chú

• Có 30% số test với 30% số điểm của bài có ~N \leq 1000~.
• Có 30% số test khác với 30% số điểm của bài có ~a_i = 1, b_i = i + 1~ với ~i = 1, 2, \dots, N - 1~.
• Có 40% số test còn lại không có ràng buộc thêm.