Lampice

Ο Mirko επέλεξε ένα χριστουγεννιάτικο δέντρο για τις εορτές που έρχονται και αποφάσισε να το στολίσει με χριστουγεννιάτικα λαμπάκια. Τα χριστουγεννιάτικα λαμπάκια περιέχουν ~N~ φωτάκια LED που συνδέονται μέσω ~(N - 1)~ αγώγιμων καλωδίων έτσι ώστε όλα τα λαμπάκια να είναι συνδεδεμένα. Επιπλέον, γνωρίζουμε το χρώμα κάθε χριστουγεννιάτικου λαμπακιού.

Αφού στόλισε το δέντρο, ο Mirko κοίταξε περήφανα το αριστούργημά του. Μετά από λίγο, άρχισε να παρατηρεί διαφορετικά μοτίβα. Μεταξύ αυτών των μοτίβων, ήταν ιδιαίτερα έκπληκτος από τα λεγόμενα παλινδρομικά τμήματα. Το παλινδρομικό τμήμα είναι ένα τμήμα χριστουγεννιάτικων λαμπτήρων στη διαδρομή μεταξύ δύο σταθερών φώτων, το ~u~ και το ~v~, έτσι ώστε η συστοιχία χρωμάτων σε μια διαδρομή από το ~u~ στο ~v~ να είναι ακριβώς η ίδια με τη σειρά των χρωμάτων στη διαδρομή από το ~v~ στο ~u~. Προσδιορίστε το μήκος του μεγαλύτερου παλινδρομικού τμήματος που εκφράζεται στον αριθμό των φώτων σε αυτό το τμήμα.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό ~N\;(1 \le N \le 50\,000)~ από την περιγραφή της εργασίας.

Η επόμενη γραμμή περιέχει μια σειρά από \(Ν\) πεζά γράμματα από το αγγλικό αλφάβητο όπου το i-οστό γράμμα αντιπροσωπεύει το χρώμα του i-οστού χριστουγεννιάτικου φωτός.

Κάθε μία από τις επόμενες ~(N - 1)~ γραμμές περιέχει δύο ακέραιους αριθμούς ~A~ και ~B\;(1 \le A, B \le N, A \ne B)~, οι οποίοι υποδηλώνουν ότι τα φώτα ~A~ και ~B~ συνδέονται απευθείας με ένα αγώγιμο σύρμα.

Έξοδος

Η πρώτη γραμμή εξόδου πρέπει να περιέχει το μήκος του μεγαλύτερου παλινδρομικού τμήματος.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	17	~N \le 3000~
2	25	Το φως ~i~ συνδέεται άμεσα με το φως ~i + 1\;(1 \le i < N)~.
3	31	Το πολύ ~100~ φώτα συνδέονται απευθείας με ακριβώς ένα άλλο φως.
4	37	Κανένας επιπλέον περιορισμός.

Παραδείγματα

input

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

output

3

input

4
aabb
1 2
1 3
3 4

output

2

input

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

output

5