Đèn trang trí

Lớp học 12A chuẩn bị cho lễ hội cuối năm. Mỗi nhóm học sinh được giao nhiệm vụ treo đèn trang trí quanh lớp học. Họ quyết định sử dụng một hệ thống dây đèn đặc biệt gồm \(N\) bóng đèn được nối với nhau bằng đúng \(N - 1\) đoạn dây dẫn điện sao cho mọi bóng đèn đều được kết nối (tức là tạo thành một cây).

Mỗi bóng đèn có một màu nhất định, biểu thị bằng một chữ cái thường từ bảng chữ cái tiếng Anh. Các bạn học sinh rất tự hào với hệ thống đèn của mình. Nhưng một học sinh tên Minh bỗng nhận thấy điều thú vị: khi đi dọc theo dây điện từ một bóng đèn \(u\) đến một bóng đèn \(v\), nếu dãy màu của các bóng đèn trên đường đi từ \(u\) đến \(v\) giống hệt với dãy từ \(v\) về \(u\), thì đoạn đó tạo nên một đường ánh sáng đối xứng.

Minh muốn biết: chiều dài lớn nhất của một đường ánh sáng đối xứng, tính theo số bóng đèn nằm trên đoạn đó.

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \leq N \leq 50000)\) --- số bóng đèn.
• Dòng thứ hai chứa một xâu gồm \(N\) chữ cái thường --- ký hiệu màu sắc của từng bóng đèn, theo thứ tự từ \(1\) đến \(N\).
• Mỗi dòng trong \(N - 1\) dòng tiếp theo chứa hai số nguyên \(A, B\) \((1 \leq A, B \leq N,\ A \neq B)\) --- biểu thị có một dây nối giữa bóng đèn \(A\) và \(B\).

Output

• Một dòng duy nhất --- độ dài lớn nhất của một đoạn ánh sáng đối xứng.

Example

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

3

4
aabb
1 2
1 3
3 4

2

Scoring

\begintabular|c|c|l|
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 15 & \(N \leq 300\)

2 & 17 & \(N \leq 3000\)

3 & 20 & Bóng đèn \(i\) nối trực tiếp với bóng đèn \(i+1\) (\(1 \le i \lt N)\)

4 & 20 & Có nhiều nhất 100 bóng đèn nối trực tiếp với đúng một bóng khác

5 & 28 & Không có ràng buộc bổ sung

\hline
\endtabular