Luna đã chọn một cây thông Noel cho kỳ nghỉ sắp tới và quyết định trang trí nó bằng đèn Giáng sinh. Đèn Giáng sinh chứa $N$ bóng đèn LED được kết nối qua $N-1$ dây dẫn sao cho tất cả các bóng đèn đều được kết nối. Ngoài ra, chúng ta biết màu sắc của mỗi bóng đèn Giáng sinh.

Sau khi trang trí cây thông, Luna tự hào nhìn ngắm kiệt tác của mình. Sau một thời gian, anh bắt đầu nhận thấy những mẫu hình khác nhau.
Trong số những mẫu hình đó, anh đặc biệt ngạc nhiên với những đoạn đối xứng. Đoạn đối xứng là một đoạn của đèn Giáng sinh trên đường đi giữa hai bóng đèn cố định, $u$ và $v$, sao cho mảng màu sắc trên đường đi từ $u$ đến $v$ hoàn toàn giống với mảng màu sắc trên đường đi từ $v$ đến $u$. Xác định độ dài của đoạn đối xứng dài nhất được biểu thị bằng số lượng bóng đèn trên đoạn đó.

Input:

• Dòng đầu tiên chứa một số nguyên $n$ $(1 \le n \le 50\,000)$ từ mô tả 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 $i$-th đại diện cho màu sắc của bóng đèn Giáng sinh thứ $i$.
• Mỗi dòng tiếp theo $n-1$ chứa hai số nguyên $u$ và $v$ $(1 \le u, v \le n, u \ne v)$, cho biết rằng bóng đèn $u$ và $v$ được kết nối trực tiếp bằng một dây dẫn.

Output:

• In ra dòng đầu tiên của đầu ra phải chứa độ dài của đoạn thẳng dài nhất.

 4
 aabb
 1 2
 1 3
 3 4

2   

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

5 

• Subtask 1:($17$%) $t \leq 3000$
• Subtask 2:($25$%) Mỗi đèn $i$ ($1 \leq i < N$) được nối trực tiếp với đèn $i+1$
• Subtask 3($31$%) Nhiều nhất 100 đèn được nối trực tiếp với đúng 1 đèn khác
• Subtask4($37$%) Không ràng buộc gì thêm