Mirko đã chọn một cây thông Noel cho dịp lễ sắp tới và quyết định trang trí nó bằng đèn Giáng sinh. Đèn Giáng sinh có ~N~ đèn LED được kết nối qua ~(N − 1)~ dây dẫn sao cho tất cả các đèn đều được kết nối với nhau. Ngoài ra, chúng ta còn biết màu của mỗi đèn Giáng sinh.

Sau khi trang trí cây, Mirko tự hào ngắm nhìn kiệt tác của mình. Một lúc sau, anh bắt đầu nhận ra các mẫu khác nhau. Trong số đó, anh đặc biệt ấn tượng bởi các đoạn gọi là đoạn ~palindrome~. Đoạn ~palindrome~ là một đoạn đèn Giáng sinh trên đường đi giữa hai đèn cố định, ~u~ và ~v~, sao cho mảng màu trên đường đi từ ~u~ đến ~v~ chính xác giống như mảng màu trên đường đi từ ~v~ đến ~u~. Xác định độ dài của đoạn palindrome dài nhất được biểu diễn bằng số lượng đèn trên đoạn đó.

Input

• Dòng đầu tiên chứa một số nguyên ~N~ ~(1 \leq N \leq 50,000)~ từ mô tả của bài toán.
• Dòng tiếp theo chứa một mảng gồm ~N~ chữ cái thường từ bảng chữ cái tiếng Anh, trong đó chữ cái thứ ~i~ đại diện cho màu của đèn Giáng sinh thứ ~i~.
• Mỗi dòng trong số ~N - 1~ dòng tiếp theo chứa hai số nguyên ~A, B~ ~(1 \leq A, B \leq N, A \ne B)~, nghĩa là ~A~ và ~B~ được kết nối trực tiếp bằng một dây dẫn.

Output

Dòng đầu tiên của đầu ra nên chứa độ dài của đoạn palindrome dài nhất.

Chú ý

• 17 điểm thỏa mãn ~N \leq 3000~.
• 25 điểm thỏa mãn đèn ~i~ được nối trực tiếp với ~i + 1~ ~(1 \leq i \leq N)~.
• 31 điểm thỏa mãn có tối đa ~100~ đèn được nối trực tiếp với một đèn khác.
• 37 điểm còn lại không có ràng buộc gì thêm.

Sample Input 1

7
imanade
1 2
2 3
3 4
4 5
5 6
6 7

Sample Ouput 1

3

Sample Input 2

4
aabb
1 2
1 3
3 4

Sample Ouput 2

2

Sample Input 3

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

Sample Ouput 3

5